Generalized Hybrid Encoding of Polyhierarchical Structures

• Autorzy: Lewandowski J. , Rybiński H.
• Języki publikacji: EN

Abstrakty

EN

Polyhierarchical structures play an important role in artificial intelligence, especially in knowledge representation. The main problem with using them efficiently is lack of efficient methods of accessing related nodes, which limits the practical applications. The proposed hybrid indexing approach generalizes various methods and makes possible combining them in a uniform manner within one index, which adapts to a particular topology of the data structure. This gives rise to a balance between compactness of the index and fast responses to the search requests. The correctness of the proposed method is formally shown, and its performance is evaluated. The results prove its high efficiency.

Słowa kluczowe

EN

knowledge representation; generalization; lattice theory; problem solving; topology; artificial intelligence; data structures

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 127, nr 1-4
• Strony: 461--477
• Opis fizyczny: Bibliogr. 36 poz., rys., tab.

Twórcy

autor

Lewandowski J.

• Institute of Computer Science, Warsaw University of Technology, Poland

autor

Rybiński H.

• Institute of Computer Science, Warsaw University of Technology, Poland

Bibliografia

• [1] Agrawal, R., Borgida, A., Jagadish, H. V.: Efficient management of transitive relationships in large data and knowledgebases, SIGMODRec., 18, June 1989,253-262.
• [2] Ait-Kaci, H., Boyer, R., Lincoln, P., Nasr, R.: Efficient implementation of lattice operations, ACM Trans. Program. Lang. Syst., 11, Jan. 1989, 115-146.
• [3] Alavi, H. S., Gilbert, S., Guerraoui, R.: Extensible encoding of type hierarchies, SIGPLAN Not., 43, Jan. 2008, 349-358.
• [4] Amagasa, T., Yoshikawa, M., Uemura, S.: QRS: A Robust Numbering Scheme for XML Documents, ICDE, IEEE Computer Society, 2003.
• [5] Baehni, S., Barreto, J. a., Eugster, P., Guerraoui, R.: Efficient distributed subtyping tests, DEBS ’07.
• [6] Bang-Jensen, Jorgen, G. G. Z.: Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics, 2nd edition, Springer Publishing Company, Incorporated, 2009.
• [7] Bloem, R., Gabow, H. N., Somenzi, F.: An Algorithm for Strongly Connected Component Analysis in n log n Symbolic Steps, FMCAD, 1954, Springer, 2000.
• [8] Bohm, C., Berchtold, S.: Multidimensional Index Structures in Relational Databases, JIIS, 15, 2000, 51-70.
• [9] Caseau, Y.: Efficient handling of multiple inheritance hierarchies, SIGPLAN Not., 28, Oct. 1993, 271-287.
• [10] Cheng, J., Yu, J. X., Lin, X., Wang, H., Yu, P. S.: Fast computation of reachability labeling for large graphs, EDBT’06, Springer-Verlag, 2006.
• [11] Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels, SODA ’02, Society for Industrial and Applied Mathematics, 2002.
• [12] Dietz, P. F.: Maintaining order in a linked list, STOC ’82, ACM, 1982.
• [13] Guttman, A.: R-trees: A Dynamic Index Structure for Spatial Searching, SIGMOD ’84, ACM, 1984.
• [14] He, H., Wang, H., Yang, J., Yu, P. S.: Compact reachability labeling for graph-structured data, CIKM ’05.
• [15] Hsu, W.-L.: PC-Trees vs. PQ-Trees, COCOON ’01, Springer-Verlag, 2001.
• [16] Jin, R., Ruan, N., Xiang, Y., Wang, H.: Path-tree: An efficient reachability indexing scheme for large directed graphs, ACMTrans. Database Syst., 36(1), March 2011, 7:1-7:44.
• [17] Krall, A., Vitek, J., Horspool, R. N.: Near optimal hierarchical encoding of types, ECOOP’97.
• [18] Lawder, J. K., King, P. J. H.: Using Space-filling Curves for Multi-dimensional Indexing, Lecture Notes in Computer Science, Springer Verlag, 2000.
• [19] Lewandowski, J., Rybinski, H.: A Hybrid Method of Indexing Multiple-Inheritance Hierarchies, ISMIS, 5722, Springer, 2009.
• [20] Li, Q., Moon, B.: Indexing and Querying XML Data for Regular Path Expressions, VLDB ’01, Morgan Kaufmann Publishers Inc., 2001.
• [21] Maier, D.: An Efficient Method for Storing Ancestor Information in Trees, SIAM J. Comput., 8(4), 1979, 599-618.
• [22] Matono, A., Amagasa, T., Yoshikawa, M., Uemura, S.: A path-based relational RDF database, ADC ’05, Australian Computer Society, Inc., 2005.
• [23] Mueck, T. A., Polaschek, M. L.: A configurable type hierarchy index for OODB, The VLDB Journal, 6, Nov. 1997, 312-332.
• [24] Preuveneers, D., Berbers, Y.: Encoding Semantic Awareness in Resource-Constrained Devices, IEEE Intelligent Systems, 23, 2008, 26-33.
• [25] Ren, Yin, G.: A Dynamic Labeling Scheme for XML Document, Journal of Communication and Computer, 3(5), 2006,61-65.
• [26] Sagan, H.: Space-Filling Curves, Springer-Verlag, 1994.
• [27] Sans, V, Laurent, D.: Prefix based numbering schemes for XML: techniques, applications and performances, Proc. VLDB Endow., 1, Aug. 2008, 1564-1573.
• [28] Schenkel, R., Theobald, A., Weikum, G.: Efficient Creation and Incremental Maintenance of the HOPI Index for Complex XML Document Collections, ICDE ’05, IEEE Computer Society, 2005.
• [29] Tarjan,R. E.: Depth-First Search and Linear Graph Algorithms, SIAMJ. Comput., 1(2), 1972, 146-160.
• [30] Tatarinov, I., Beyer, K., Shanmugasundaram, J.: Storing and querying ordered xml using a relational database system, In SIGMOD, 2002.
• [31] Thonangi, R.: A Concise Labeling Scheme for XML Data, COMAD, Tata McGraw-Hill Publishing Company Limited, 2006.
• [32] Trissl, S., Leser, U.: Fast and practical indexing and querying of very large graphs, SIGMOD ’07.
• [33] Wang, H., He2, H., Yang, J., Yu, P. S., Yu, J. X.: Dual Labeling: Answering Graph Reachability Queries in Constant Time, ICDE ’06, IEEE Computer Society, 2006.
• [34] Wang, J., Wu, S., Gao, H., Li, J., Ooi, B. C.: Indexing multi-dimensional data in a cloud system, SIGMOD ’10, ACM, 2010.
• [35] Wu, X., Lee, M. L., Hsu, W.: A Prime Number Labeling Scheme for Dynamic Ordered XML Trees, ICDE ’04, IEEE Computer Society, 2004.
• [36] Zibin, Y., Gil, J. Y.: Efficient subtyping tests with PQ-encoding, SIGPLANNot., 36, Oct. 2001, 96-107.