research-article

On the Signature Tree Construction and Analysis

Author:

Yibin ChenAuthors Info & Claims

IEEE Transactions on Knowledge and Data Engineering, Volume 18, Issue 9

Pages 1207 - 1224

https://doi.org/10.1109/TKDE.2006.146

Published: 01 September 2006 Publication History

Abstract

Advanced database application areas, such as computer aided design, office automation, digital libraries, data-mining, as well as hypertext and multimedia systems, need to handle complex data structures with set-valued attributes, which can be represented as bit strings, called signatures. A set of signatures can be stored in a file, called a signature file. In this paper, we propose a new method to organize a signature file into a tree structure, called a signature tree, to speed up the signature file scanning and query evaluation. In addition, the average time complexity of searching a signature tree is analyzed and how to maintain a signature tree on disk is discussed. We also conducted experiments, which show that the approach of signature trees provides a promising index structure.

References

[1]

Int'l J. Digital Libraries, vol. 1, no. 1, pp. 5-19, Jan. 1997.

[2]

A.V. Aho, J.E. Hopcroft, and J.D. Ullman, The Design and Analysis of Computer Algorithms. London: Addison-Wesley Publishing Company, 1974.

[3]

Rudolf Bayer, Karl Unterauer, Prefix B-trees, ACM Transactions on Database Systems (TODS), v.2 n.1, p.11-26, March 1977

Digital Library

[4]

W.W. Chang and H.J. Schek, “A Signature Access Method for the STARBURST Database System,” Proc. 19th Very Large Data Bases Conf., pp. 145-153, 1989.

[5]

Y. Chen and Y.B. Chen, “Signature File Hierarchies and Signature Graphs: A New Indexing Method for Object-Oriented Datbases,” Proc. ACM Symp. Applied Computing (SAC '04), pp. 724-728, 2004.

Digital Library

[6]

S. Christodoulakis and C. Faloutsos, “Design Consideration for a Message File Server,” IEEE Trans. Software Eng., vol. 10, no. 2, pp. 201-210, 1984.

Digital Library

[7]

S. Christodoulakis, M. Theodoridou, F. Ho, M. Papa, A. Pathria, Multimedia document presentation, information extraction, and document formation in MINOS: a model and a system, ACM Transactions on Information Systems (TOIS), v.4 n.4, p.345-383, Oct. 1986

Digital Library

[8]

R.V. Churchill, Operational Mathematics. New York: McGraw-Hill Book Company, 1958.

[9]

Paolo Ciaccia, Paolo Tiberio, Pavel Zezula, Declustering of key-based partitioned signature files, ACM Transactions on Database Systems (TODS), v.21 n.3, p.295-338, Sept. 1996

Digital Library

[10]

M. Crochemore and W. Rytter, Text Algorithms. New York: Oxford Univ. Press, 1994.

[11]

U. Deppisch, “S-Tree: A Dynamic Balanced Signature Index for Office Retrieval,” Proc. ACM SIGIR Conf., pp. 77-87, Sept. 1986.

Digital Library

[12]

J. Information Processing Letters 65, pp. 101-106, 1998.

[13]

Chris Faloutsos, Access methods for text, ACM Computing Surveys (CSUR), v.17 n.1, p.49-74, March 1985

Digital Library

[14]

C. Faloutsos and R. Chan, “Fast Text Access Methods for Optical and Large Magnetic Disks: Designs and Performance Comparison,” Proc. 14th Int'l Conf. Very Large Data Bases, pp. 280-293, Aug. 1988.

[15]

C. Faloutsos, “Signature Files,” Information Retrieval: Data Structures & Algorithms, W.B. Frakes and R. Baeza-Yates, eds., pp. 44-65, New Jersey: Prentice Hall, 1992.

Digital Library

[16]

C. Faloutsos, R. Lee, C. Plaisant, and B. Shneiderman, “Incorporating String Search in Hypertext System: User Interface and Signature File Design Issues,” HyperMedia, vol. 2, no. 3, pp. 183-200, 1990.

[17]

Philippe Flajolet, Claude Puech, Partial match retrieval of multidimensional data, Journal of the ACM (JACM), v.33 n.2, p.371-407, April 1986

Digital Library

[18]

D. Harman, E. Fox, and R. Baeza-Yates, “Inverted Files,” Information Retrieval: Data Structures & Algorithms, W.B. Frakes and R. Baeza-Yates, eds., pp. 28-43, New Jersey: Prentice Hall, 1992.

[19]

Y. Ishikawa, H. Kitagawa, and N. Ohbo, “Evaluation of Signature Files as Set Access Facilities in OODBs,” Proc. ACM SIGMOD Int'l Conf. Management of Data, pp. 247-256, May 1993.

Digital Library

[20]

D.E. Knuth, The Art of Computer Programming: Sorting and Searching. London: Addison-Wesley Pub., 1973.

[21]

J. Am. Soc. Information Science, vol. 41, no. 7, pp. 508-534, 1990.

[22]

S. Kocberber and F. Can, “Compressed Multi-Framed Signature Files: An Index Structure for Fast Information Retrieval,” Proc. ACM Symp. Applied Computing (SAC '99), pp. 221-226, 1999.

Digital Library

[23]

D.L. Lun, Y.M. Kim, and G. Patel, “Efficient Signature File Methods for Text Retrieval,” IEEE Trans. Knowledge and Data Eng., vol. 7, no. 3, June 1995.

Digital Library

[24]

W. Lee and D.L. Lee, “Signature File Methods for Indexing Object-Oriented Database Systems,” Proc. ICIC '92— Second Int'l Conf. Data and Knowledge Eng.: Theory and Application, pp. 616-622, Dec. 1992.

[25]

Donald R. Morrison, PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric, Journal of the ACM (JACM), v.15 n.4, p.514-534, Oct. 1968

Digital Library

[26]

J. Riordan, Comninatorial Identities. New York: Wiley, 1968.

[27]

Computer J., vol. 43, no. 4, pp. 301-314, 2000.

[28]

Infromation Systems, vol. 27, no. 2, pp. 93-121, 2002.

[29]

Proc. 10th Int'l Conf. Data Eng., pp. 518-525, Feb. 1994.

[30]

Justin Zobel, Alistair Moffat, Kotagiri Ramamohanarao, Inverted files versus signature files for text indexing, ACM Transactions on Database Systems (TODS), v.23 n.4, p.453-490, Dec. 1998

Digital Library

Cited By

Nowaková JPrílepok MSnášel V(2017)Medical Image Retrieval Using Vector Quantization and Fuzzy S-treeJournal of Medical Systems10.1007/s10916-016-0659-241:2(1-16)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1007/s10916-016-0659-2
(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
https://dl.acm.org/doi/10.1016/j.tcs.2016.07.018
Korpal RGopal AMishra B(2011)A comparative study of signature based indexes for efficient retrieval of temporal patternsProceedings of the International Conference & Workshop on Emerging Trends in Technology10.1145/1980022.1980104(382-387)Online publication date: 25-Feb-2011
https://dl.acm.org/doi/10.1145/1980022.1980104
Show More Cited By

Index Terms

On the Signature Tree Construction and Analysis

Recommendations

On the Signature Trees and Balanced Signature Trees
ICDE '05: Proceedings of the 21st International Conference on Data Engineering

Advanced database application areas, such as computer aided design, office automation, digital libraries, data-mining as well as hypertext and multimedia systems need to handle complex data structures with set-valued attributes, which can be represented ...
A comparative study of signature based indexes for efficient retrieval of temporal patterns
ICWET '11: Proceedings of the International Conference & Workshop on Emerging Trends in Technology

This paper presents a comparative study of signature based indexing techniques applied to a database of temporal patterns. Temporal patterns include a set of states and relationships among the states. Signature-based indexing was used to accommodate ...
On the cost of searching signature trees

A precise analysis of the retrieval of signature trees is presented. A signature tree is a data structure constructed over a signature file to speed up searching all those signatures, which match a given query signature. The methods used include a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Knowledge and Data Engineering

IEEE Transactions on Knowledge and Data Engineering Volume 18, Issue 9

September 2006

144 pages

ISSN:1041-4347

Issue’s Table of Contents

Copyright © 2006.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 September 2006

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nowaková JPrílepok MSnášel V(2017)Medical Image Retrieval Using Vector Quantization and Fuzzy S-treeJournal of Medical Systems10.1007/s10916-016-0659-241:2(1-16)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1007/s10916-016-0659-2
(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
https://dl.acm.org/doi/10.1016/j.tcs.2016.07.018
Korpal RGopal AMishra B(2011)A comparative study of signature based indexes for efficient retrieval of temporal patternsProceedings of the International Conference & Workshop on Emerging Trends in Technology10.1145/1980022.1980104(382-387)Online publication date: 25-Feb-2011
https://dl.acm.org/doi/10.1145/1980022.1980104
Hossain SJamil H(2010)A hybrid index structure for set-valued attributes using itemset tree and inverted listProceedings of the 21st international conference on Database and expert systems applications: Part I10.5555/1881867.1881905(349-357)Online publication date: 30-Aug-2010
https://dl.acm.org/doi/10.5555/1881867.1881905
Shanthi IIzaaz YNadarajan RShyamasundar R(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
https://dl.acm.org/doi/10.1145/1341771.1341786

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents