Nothing Special   »   [go: up one dir, main page]

skip to main content
article

Signature-based structures for objects with set-valued attributes

Published: 01 April 2002 Publication History

Abstract

Aiming at the efficient retrieval of objects with set-valued attributes, we introduce three variations of a new method in order to satisfy subset and superset queries. Our approach is to combine the advantages of two access methods, that of linear Hashing and of tree-shaped methods, on which other similar methods have been previously reported as well. Performance estimation analytical functions for each particular method are presented, followed by a thorough experimental comparison of all investigated structures, where analytical and experimental results deviate 10% on the average. Finally, the results of this performance evaluation are presented and discussed, clearly showing the superiority of the new methods reaching an improvement of up to 85%.

References

[1]
{1} E. Bertino, B. Catania, L. Chiesa, Definition and analysis of index organizations for object-oriented database systems, Inf. Systems 23 (2) (1998) 65-108.
[2]
{2} E. Bertino, B.C. Ooi, R. Sacks-Davis, K.L Tan, J. Zobel, B. Shidlovsky, B. Catania, Indexing Techniques for Advanced Database Systems, Kluwer Academic Publishers, Dordrecht, 1997.
[3]
{3} A. Kemper, G. Moerkotte, Access support relations: an indexing method for object bases, Inf. Systems 17 (2) (1992) 117-146.
[4]
{4} T.A. Mueck, M.L. Polaschek, Index data structures in object-oriented databases, Kluwer Academic Publishers, Dordrecht, 1997.
[5]
{5} Z. Xie, J. Han, Join index hierarchies for supporting efficient navigation in object-oriented databases, Proceedings of the 20th VLDB Conference, Santiago, Chile, 1994, pp. 522-533.
[6]
{6} S. Christodoulakis, C. Faloutsos, Signature files: an access method for documents and its analytical performance evaluation, ACM Trans. Office Inf. Systems 2 (4) (1984) 267-288.
[7]
{7} C. Faloutsos, Signature files, in: W.B. Frakes, R. Baeza-Yates (Eds.), Information Retrieval: Data Structures and Algorithms, Prentice-Hall, Englewood Cliffs, NJ, 1992.
[8]
{8} D. Dervos, Y. Manolopoulos, P. Linardis, Comparison of signature file models with superimposed coding, Inf. Process. Lett. 65 (2) (1998) 101-106.
[9]
{9} S. Kocberber, F. Can, J. Paton, Optimization of signature file parameters with varying record lengths, Comput. J. 42 (1) (1999) 11-23.
[10]
{10} Y. Ishikawa, H. Kitagawa, N. Ohbo, Evaluation of signature files as set access facilities in OODBs, Proceedings of the 1993 ACM SIGMOD Conference, Washington, DC, 1993, pp. 247-256.
[11]
{11} H. Kitagawa, Y. Fukushima, Y. Ishikawa, N. Ohbo, Estimation of false drops in set-valued object retrieval with signature files, Proceedings of the Fourth FODO Conference, Chicago, IL, 1993, pp. 146-163.
[12]
{12} H. Kitagawa, N. Watanabe, Y. Ishikawa, Design and evaluation of signature file organization incorporating vertical and horizontal decomposition schemes, Proceedings of the Seventh DEXA Conference, Zurich, Switzerland, 1996, pp. 875-888.
[13]
{13} P. Ciaccia, P. Tiberio, P. Zezula, Declustering of key-based partitioned signature files, ACM Trans. Database Systems 21 (3) (1996) 295-338.
[14]
{14} D.L. Lee, C.W. Leng, Partitioned signature files: design issues and performance evaluation, ACM Trans. Office Inf. Systems 7 (2) (1989) 158-180.
[15]
{15} D.L. Lee, C.W. Leng, A partitioned signature file structure for multiattribute and text retrieval, Proceedings of the Sixth ICDE Conference, Los Angeles, CA, 1990, pp. 389-397.
[16]
{16} P. Zezula, F. Rabitti, P. Tiberio, Dynamic partitioning of signature files, ACM Trans. Inf. Systems 9 (4) (1991) 336 369.
[17]
{17} P. Bozanis, C. Makris, A. Tsakalidis, Parametric weighted filter: an efficient dynamic manipulation of signature files, Comput. J. 38 (6) (1995) 478-488.
[18]
{18} R. Sacks-Davis, K. Ramamohanarao, A two level superimposed coding scheme for partial match retrieval, Inf. Systems 8 (4) (1983) 273-289.
[19]
{19} J. Pfaltz, W. Berman, E. Cagley, Partial match retrieval using indexed descriptor files, Commun. ACM 23 (9) (1980) 522-528.
[20]
{20} U. Deppisch, S-tree: a dynamic balanced signature index for office retrieval, Proceedings of the Ninth ACM SIGIR Conference, Pisa, Italy, 1986, pp. 77-87.
[21]
{21} E. Tousidou, A. Nanopoulos, Y. Manolopoulos, Improved methods for signature tree construction, Comput. J. 43 (4) (2000) 301-314.
[22]
{22} J.M. Hellerstein, A. Pfeffer, The RD-tree: an index structure for sets, Technical Report No. 1252, University of Wisconsin at Madison, 1994.
[23]
{23} S. Helmer, G. Moerkotte, Evaluation of main memory join algorithms for joins with set comparison join predicates, Proceedings of the 23rd VLDB Conference, Athens, Greece, 1997, pp. 386-395.
[24]
{24} W.C. Lee, D.L. Lee, Signature file methods for indexing object-oriented database systems, Proceedings of the Second Computer Science Conference, Hong Kong, 1992, pp. 616-622.
[25]
{25} H.S. Yong, S. Lee, H.J. Kim, Applying signatures for forward traversal query processing in object-oriented databases, Proceedings of the 10th ICDE Conference, Houston, Texas, 1994, pp. 518-525.
[26]
{26} K. Ramasamy, J.M. Patel, J.F. Naughton, R. Kaushik, Set containment joins: the good, the bad and the ugly, Proceedings of the 26th VLDB Conference, Cairo, Egypt, 2000, pp. 351-362.
[27]
{27} W. Litwin, Linear Hashing: a new tool for files and table addressing, Proceedings of the Sixth VLDB Conference, Montreal, Canada, 1980, pp. 212-223.
[28]
{28} W. Litwin, M.A. Neitman, D.A. Schneider, LH* --linear hashing for distributed files, ACM Trans. Database Systems 21 (4) (1996) 480-525
[29]
{29} F. Grandi, P. Tiberio, P. Zezula, Frame-sliced partitioned parallel signature files, Proceedings of the 15th ACM SIGIR Conference, Copenhagen, Denmark, 1992, pp. 286-297.
[30]
{30} E. Tousidou, M. Vassilakopoulos, Y. Manolopoulos, Performance evaluation of parallel S-trees, J. Database Manage. 11 (3) (2000) 28-34.

Cited By

View all

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information Systems
Information Systems  Volume 27, Issue 2
Databases: Creation, management and utilization
April 2002
73 pages

Publisher

Elsevier Science Ltd.

United Kingdom

Publication History

Published: 01 April 2002

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 20 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2019)A novel subgraph querying method based on paths and spectraNeural Computing and Applications10.1007/s00521-018-3837-y31:9(5671-5678)Online publication date: 1-Sep-2019
  • (2016)An efficient method to evaluate intersections on big data setsTheoretical Computer Science10.1016/j.tcs.2016.07.018647:C(1-21)Online publication date: 27-Sep-2016
  • (2014)gStoreThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-013-0337-723:4(565-590)Online publication date: 1-Aug-2014
  • (2011)gStoreProceedings of the VLDB Endowment10.14778/2002974.20029764:8(482-493)Online publication date: 1-May-2011
  • (2010)On index structures in hybrid metaheuristics for routing problems with hard feasibility checksProceedings of the 7th international conference on Hybrid metaheuristics10.5555/1926965.1926977(160-173)Online publication date: 1-Oct-2010
  • (2009)An efficient signature-based strategy for supporting inexact filtering in information filtering systemsExpert Systems with Applications: An International Journal10.1016/j.eswa.2008.10.07436:4(8431-8442)Online publication date: 1-May-2009
  • (2008)Summarization graph indexingProceedings of the 13th international conference on Database systems for advanced applications10.5555/1802514.1802532(141-155)Online publication date: 19-Mar-2008
  • (2008)A novel spectral coding in a large graph databaseProceedings of the 11th international conference on Extending database technology: Advances in database technology10.1145/1353343.1353369(181-192)Online publication date: 25-Mar-2008
  • (2008)On the SD-tree construction for optimal signature operationsProceedings of the 1st Bangalore Annual Compute Conference10.1145/1341771.1341786(1-8)Online publication date: 18-Jan-2008
  • (2007)Indexing set-valued attributes with a multi-level extendible hashing schemeProceedings of the 18th international conference on Database and Expert Systems Applications10.5555/2395856.2395871(98-108)Online publication date: 3-Sep-2007
  • Show More Cited By

View Options

View options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media