nach oben

Journal of Intelligent Information Systems

Erschienen in:

24.09.2015

Classifying and querying very large taxonomies with bit-vector encoding

verfasst von: Hassan Aït-Kaci, Samir Amir

Erschienen in: Journal of Intelligent Information Systems | Ausgabe 1/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this article, we address the question of how efficiently Semantic Web (SW) reasoners perform in processing (classifying and querying) taxonomies of enormous size and whether it is possible to improve on existing implementations. We use a bit-vector encoding technique to implement taxonomic concept classification and Boolean-query answering. We describe the technique we have used, which achieves high performance, and discuss implementation issues. We compare the performance of our implementation with those of the best existing SW reasoning systems over several very large taxonomies under the exact same conditions for so-called TBox reasoning. The results show that our system is among the best for concept classification and several orders-of-magnitude more efficient in terms of response time for query answering. We present these results in detail and comment them. We also discuss pragmatic issues such as cycle detection and decoding.

Nächster Artikel A data-driven passing interaction model for embodied basketball agents

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

In Semantic Web lingo, a Knowledge Base (KB) is defined as a formal ontology consisting of two parts (or “boxes”): (1) a Terminological Box (abbreviated as TBox); and, (2) an Assertional Box (abbreviated as ABox). The TBox contains the formal axioms that define the structure and semantic properties of the actual instance data; which instance data constitute the ABox. In Database lingo, the TBox corresponds to the schema and the ABox to the actual data.

http://www.cs.ox.ac.uk/isg/tools/ELK/

http://code.google.com/p/cel/

http://code.google.com/p/cb-reasoner/

http://owl.cs.manchester.ac.uk/fact++/

http://www.hermit-reasoner.com/

http://clarkparsia.com/pellet/

http://trowl.eu/

http://www.racer-systems.com/products/racerpro/

http://research.ict.csiro.au/software/snorocket

Description Logics in the \(\mathcal {EL}\)-family are weaker versions that provide existential roles (∃r.C) but no universal roles (∀r.C).

To the best of our knowledge, this is the latest best bound as of 2011. However, these algorithms are not implementable due to prohibitive size of constants. For more recent work on parallelizing Strassen’s algorithm, see (Ballard et al. 2014). This, however, requires special harware (GPGPUs).

op. cit., pages 125–126.

See Section 4.2.

http://www.h-its.org/en/research/nlp/wikitaxonomy/

http://bioportal.bioontology.org/ontologies/3022

http://www.nlm.nih.gov/mesh/meshhome.html

http://www.ncbi.nlm.nih.gov/Taxonomy/taxonomyhome.html/

See Section 3.3 for a discussion concernining this point.

We use “ &” to denote “and,” and “ |” to denote “or.”

We implemented such a facility—see Appendix.

http://en.wikipedia.org/wiki/Quicksort

The ordering on bit-vector codes is simply defined as c ₁≤c ₂ iff c ₁=c ₁ & c ₂.

In the same manner as we have noticed that SnoRocket does.

http://cedar.liris.cnrs.fr/data/CEDAR-V1.0.zip

http://cedar.liris.cnrs.fr/demos.html

Recall that a bit vector is written with its lowest bit to the right.

In what follows, we shall use the “dot” notation of object-oriented methods to denote all functions or operations on codes.

Note that i≠j implies necessarily that i<j (by Condition (1) and since n<m).

Actually, the java.util.TreeSet does maintain a doubly-linked list for its elements in order to ensure its two ordered iterators (ascending and descending). But this structure is not made public and one cannot splice in new elements from a given found element. But it is a simple matter to modify the source code of java.util.TreeSet.java and adapt it to what is needed.

In fact, they see that only as a possible a posteriori optimization, but one that would cause their optimal spanning-tree finding algorithm to be incorrect if applied incrementally while it is executed.

Agrawal, R., Borgida, A., & Jagadish, H. V. (1989). Efficient management of transitive relationships in large data and knowledge bases. In J. Clifford, B.G. Lindsay, & D. Maier (Eds.), Proceedings of the ACM SIGMOD International Conference on Management of Data. [Available online http://dbs.informatik.uni-halle.de/Lehre/DBS_IIa_SS02/p253-agrawal.pdf]., (Vol. 18(2) pp. 253–262). Portland: ACM, SIGMOD Record.

Aït-Kaci, H. (1991). Warren’s Abstract Machine: A Tutorial Reconstruction. Cambridge: The MIT Press. [Available online http://wambook.sourceforge.net/].

Aït-Kaci, H. (2007). Data models as constraint systems—A key to the Semantic Web. Constraint Processsing Letters, 1(1), 33–88. [Available online http://www.cs.brown.edu/people/pvh/CPL/Papers/v1/hak.pdf].

Aït-Kaci, H., & Amir, S. (2013). Classifying and querying very large taxonomies—a comparative study to the best of our knowledge. \(\mathcal {CEDAR}\) Technical Report Number 2, \(\mathcal {CEDAR}\) Project, LIRIS, Département d’Informatique, Université Claude Bernard Lyon 1, Villeurbanne, France. [Available online http://cedar.liris.cnrs.fr/papers/ctr2.pdf].

Aït-Kaci, H., Boyer, R., Lincoln, P., & Nasr, R. (1989). Efficient implementation of lattice operations. ACM Transactions on Programming Languages and Systems, 11 (1), 115–146. [Available online http://hassan-ait-kaci.net/pdf/encoding-toplas-89.pdf].CrossRef

Aït-Kaci, H, & Di Cosmo, R. (1993). Compiling order-sorted feature term unification Vol. 7. France: PRL Technical Note, Digital Paris Research Lab, Rueil-Malmaison. [Available online http://hassan-ait-kaci.net/pdf/PRL-TN-7.pdf].

Amir, S., & Aït-Kaci, H. (2013). CEDAR: a fast taxonomic reasoner based on lattice operations. In Proceedings of the ISWC 2013 Posters & Demonstrations Track, Sydney, Australia (pp. 9–12).

Amir, S., & Aït-Kaci, H. (2014a). CEDAR: efficient reasoning for the semantic web. In Tenth International Conference on Signal-Image Technology and Internet-Based Systems, SITIS 2014 (pp. 157–163), Marrakech, Morocco.

Amir, S., & Aït-Kaci, H. (2014b). Design and implementation of an efficient semantic web reasoner. CEDAR Technical Report Number 12, \(\mathcal {CEDAR}\) Project, LIRIS, Département d’Informatique, Université Claude Bernard Lyon Vol. 1, Villeurbanne, France. [Available online http://cedar.liris.cnrs.fr/papers/ctr12.pdf].

Baader, F., Brandt, S., & Lutz, C. (2005). Pushing the \(\mathcal {EL}\) envelope. In L. P. Kaelbling, & A. Saffiotti (Eds.), Proceedings of the 19th International Joint Conference on Artificial Intelligence (pp. 364–369). Edinburgh: IJCAI’05, Morgan Kaufmann Publishers. [Available online http://www.ijcai.org/papers/0372.pdf]

Baader, F., Lutz, C., & Suntisrivaraporn, B. (2006). CEL—a polynomial-time reasoner for life science ontologies. In U. Furbach, & N. Shankar (Eds.), Proceedings of the 3rd international joint conference on automated reasoning, (Vol. 4130 pp. 287–291). Seattle: IJCAR’06, Springer-Verlag LNAI. [Available online http://lat.inf.tu-dresden.de/research/papers/2006/BaaLutSun-IJCAR-06.pdf].

Ballard, G., Demmel, J., Holtz, O., & Schwartz, O. (2014). Communication costs of Strassen’s matrix multiplication. Communications of the ACM, 57(2), 107–114. [Available online https://aspire.eecs.berkeley.edu/wp/wp-content/uploads/2014/02/Communication-Costs-of-Strassen%E2%80%99s-Matrix-Multiplication.pdf].

Coppersmith, D., & Winograd, S. (1990). Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9(3), 251–280. [Available online http://www.sciencedirect.com/science/article/pii/S0747717108800132].MathSciNetCrossRefMATH

Cousot, P. (1996). Abstract interpretation. ACM Computing Surveys—Symposium on Models of Programming Languages and Computation, 28(2), 324–328. Tutorial summary: [Available online http://www.di.ens.fr/~cousot/AI/IntroAbsInt.html].

Fikes, R., Hayes, P., & Horrocks. I. (2004). OWL-QL—a language for deductive query answering on the Semantic Web. Journal of Web Semantics, 2(1), 19–29. [Available online http://www.sciencedirect.com/science/article/pii/S1570826804000137].CrossRef

Fischer, M. J., & Meyer, A. R. (1971). Boolean matrix multiplication and transitive closure. In Proceedings of the 12th annual symposium on switching and automata theory, SWAT’71, (pp. 129–131), Washington: IEEE Computer Society. [Available online http://rjlipton.files.wordpress.com/2009/10/matrix1971.pdf].

Haarslev, V., Hidde, K., Möller, R., & Wessel, M. (2011). The RacerPro knowledge representation and reasoning system. Semantic Web Journal, 1, 1–11. [Available online http://www.semantic-web-journal.net/sites/default/files/swj109_3.pdf].

Haarslev, V., & Möller, R. (2001). RACER system description. In R. Gore, A. Leitsch, & T. Nipkow (Eds.), Proceedings of the 1st international joint conference on automated reasoning (pp. 701–706). Siena: IJCAR’01, Springer-Verlag. [Available online https://www.ifis.uni-luebeck.de/~moeller/papers/2001/HaMo01a.pdf].

Hoare, C. A. R. (1961). Algorithm 63: Partition, algorithm 64: Quicksort. Communications of the ACM, 4(7), 321–321. [Available online http://comjnl.oxfordjournals.org/content/5/1/10.full.pdf].CrossRef

Horrocks, I., & Sattler. U. (2007). A tableau decision procedure for \(\mathcal {SHOIQ}\). Journal of Automated Reasoning, 39 (3), 249–276. [Available online http://www.cs.ox.ac.uk/ian.horrocks/Publications/download/2007/HoSa07a.pdf].MathSciNetCrossRefMATH

Kazakov, Y. (2009). Consequence-driven reasoning for horn \(\mathcal {SHIQ}\) ontologies. In C. Boutilier (Ed.), Proceedings of the 21st international conference on artificial intelligence (pp. 2040–2045). Pasadena: IJCAI’09, Association for the Advancement of Artificial Intelligence. [Available online http://ijcai.org/papers09/Papers/IJCAI09-336.pdf].

Kazakov, Y., Krötzsch, M., & Simančík, F. (2011). Unchain my \(\mathcal {EL}\) reasoner. In R. Rosati, S. Rudolph, & M. Zakharyaschev (Eds.), Proceedings of the 24th international workshop on description logics. Barcelona: DL’11, CEUR Workshop Proceedings. [Available online http://ceur-ws.org/Vol-745/paper_54.pdf].

Lawley, M. J., & Bousquet, C. (2010). Fast classification in Protegé́: Snorocket as an OWL 2 EL reasoner. In T. Meyer, M. A. Orgun, & K. Taylor (Eds.), Proceedings of the 2nd Australasian ontology workshop: Advances in ontologies. (pp. 45–50). Adelaide: AOW’10, ACS. [Available online http://krr.meraka.org.za/~aow2010/Lawley-etal.pdf].

Manna, Z., & Waldinger, R. (1991). Fundamentals of deductive program synthesis. In A. Apostolico, & Z. Galil (Eds.), Combinatorial algorithms on words, NATO ISI Series: Springer. [Available online http://lara.epfl.ch/~kuncak/t/MannaWaldingerTSE.pdf].

Motik, B., Shearer, R., & Horrocks, I. (2009). Hypertableau reasoning for description logics. Journal of Artificial Intelligence Research, 36(1), 165–228. [Available online https://www.jair.org/media/2811/live-2811-4689-jair.pdf].MathSciNetMATH

Shearer, R., Motik, B., & Horrocks, I. (2008). HermiT: A highly-efficient OWL reasoner. In U. Sattler, & C. Dolbear (Eds.), Proceedings of the 5th international workshop on OWL experiences and directions Karlsruhe: OWLED’08, CEUR Workshop Proceedings. [Available online http://www.cs.ox.ac.uk/ian.horrocks/Publications/download/2008/ShMH08b.pdf].

Sirin, E., Parsia, B., Grau, B. C., Kalyanpur, A., & Katz, Y. (2007). Pellet: A practical OWL-DL reasoner. Journal of Web Semantics, 5(2), 51–53. This is a summary; full paper: [Available online http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.96.5433&rep=rep1&type=pdf].

Stothers, A. (2010). On the complexity of matrix multiplication. Edinburgh: PhD thesis, University of Edinburgh. [Available online http://www.maths.ed.ac.uk/assets/files/pgrexternalfiles/theses/probability/stothers.pdf].

Strassen, V. (1969). Gaussian elimination is not optimal. Numerische Mathematik, 13, 354–356.MathSciNetCrossRefMATH

Thomas, E., Pan, J. Z., & Ren, Y. (2010). TrOWL: Tractable OWL 2 reasoning infrastructure. In L. Aroyo, G. Antoniou, E. Hyvnen, A. ten Teije, H. Stuckenschmidt, L. Cabral, & T. Tudorache (Eds.), Proceedings of the 7th extended semantic web conference (pp. 431–435). Heraklion: ESWC’10, Springer. [Available online http://homepages.abdn.ac.uk/jeff.z.pan/pages/pub/TPR2010.pdf].

Tsarkov, D., & Horrocks, I. (2006). FaCT++ description logic reasoner: System description. In U. Furbach, & N. Shankar (Eds.), Proceedings of the 3rd international joint conference on automated reasoning. [Available online http://www.cs.ox.ac.uk/Ian.Horrocks/Publications/download/2006/TsHo06a.pdf]. (pp. 292–297). Seattle: IJCAR’06, Springer.

Warren Jr, H. S. (1975). A modification of Warshall’s algorithm for the transitive closure of binary relations. Communications of the ACM, 18(4), 218–220. [Available online http://dl.acm.org/citation.cfm?id=360746].

Warshall, S. (1962). A theorem on Boolean matrices. Journal of the ACM, 9(1), 11–12.MathSciNetCrossRefMATH

Williams, V. V. (2011). Breaking the Coppersmith-Winograd barrier: University of California at Berkeley and Stanford University. [Available online http://www.cs.rit.edu/~rlc/Courses/Algorithms/Papers/matrixMult.pdf].

Titel: Classifying and querying very large taxonomies with bit-vector encoding
verfasst von: Hassan Aït-Kaci
Samir Amir
Publikationsdatum: 24.09.2015
Verlag: Springer US
Erschienen in: Journal of Intelligent Information Systems / Ausgabe 1/2017
Print ISSN: 0925-9902
Elektronische ISSN: 1573-7675
DOI: https://doi.org/10.1007/s10844-015-0383-2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2017

Two-tier network anomaly detection model: a machine learning approach

Intelligent information processing for building university knowledge base

A data-driven passing interaction model for embodied basketball agents

A just-in-time keyword extraction from meeting transcripts using temporal and participant information

Multilingual news extraction via stopword language model scoring

Efficient pruning for top-K ranking queries on attribute-wise uncertain datasets

Premium Partner