article

Free access

Signature files: an access method for documents and its analytical performance evaluation

Editor: John O. Limb Authors:

Chris Faloutsos,

Stavros ChristodoulakisAuthors Info & Claims

ACM Transactions on Information Systems (TOIS), Volume 2, Issue 4

Pages 267 - 288

https://doi.org/10.1145/2275.357411

Published: 01 October 1984 Publication History

PDF eReader

References

[1]

AHO, A. V., AND CORASICK, M.J. Efficient string matching: An aid to bibliographic search. Commun. ACM 18, 6 (June 1975), 333-340.

Crossref

Google Scholar

[2]

AIqGELL, R. C., FREUND, G. E., AND WILLET, P. Automatic spelling correction using a trigram similarity measure. Inf. Proc. Manage. 19, 4 (1983), 255-261.

Google Scholar

[3]

BIRD, R. M., Tu, J. C., AND WORTHY, R.M. Associative/parallel processors for searching very large textual data bases. In Proceedings of the 3rd A CM Workshop on Computer Architecture {or Non-numeric Processing, {May). ACM, New York, 1977, pp. 8-16.

Crossref

Google Scholar

[4]

BOYER, R. S., AND MOORE, J.S. A fast string searching algorithm. Commun. ACM 20, 10 (Oct. 1977), 762-772.

Crossref

Google Scholar

[5]

CARDENAS, A.F. Analysis and performance of inverted data base structures. Commun. ACM 18, 5 (May 1975), 253-263.

Crossref

Google Scholar

[6]

CHRISTODOULAKIS, S. Estimating block transfers and join sizes. In SIGMOD 83 Proceedings. SIGMOD Rec. 13, 4 (May 1983), 40-54.

Crossref

Google Scholar

[7]

CHRISTODOULAKIS, S. A framework for the development of a mixed-mode message system for an office environment. In Proceedings of the 3rd Joint ACM-BCS Symposium on Research and Development in Information Retrieval (1984). to appear.

Crossref

Google Scholar

[8]

CHRISTODOULAKIS, S., AND FALOUTSOS, C. Design considerations for a message file server. IEEE Trans. Softw. Eng. SE-IO, 2 (March 1984), 201-210.

Google Scholar

[9]

DATTOt, A, R. FIRST: flexible information retrieval system for text. J. Am. Soc. Inf. Sci. 30, (Jan. 1979), 9-14.

Google Scholar

[10]

DEWEY, C. Relative Frequency of English Speech Sounds. Harvard University Press, Cambridge, Mass., 1950.

Google Scholar

[11]

GONNET, G.H. Unstructured Data Bases. Tech. Rep. CS-82-09, Computer Science Dept., Univ. of Waterloo, Waterloo, Canada, 1982.

Google Scholar

[12]

HARRISON, M.C. Implementation of the substring test by hashing. Commun. ACM 14, 12 (Dec. 1971), 777-779.

Crossref

Google Scholar

[13]

HASKIN, R.L. Special-purpose processors for text retrieval. Database Eng. 4, 1 (Sept. 1981), 16-29.

Google Scholar

[14]

HASKXN, R. L., AND LOmE, R.A. On extending the functions of a relational database system. Proc. ACM SIGMOD. ACM, New York, 1982, pp. 207-212.

Crossref

Google Scholar

[15]

HOLLAAR, L.A. Text retrieval computers. IEEE Computer 12, 3 (Mar. 1979), 40-50.

Google Scholar

[16]

HOLLAAR, L. A., SMITH, K. F., CHOW, W. H., EMRATH, P. A., AND HASKIN, R.L. Architecture and operation of a large, full-text information-retrieval system. In Advanced Database Machine Architecture, D. K. Hsiao, Ed. Prentice-Hall, Englewood Cliffs, N.J., 1983, pp. 256-299.

Google Scholar

[17]

IBM. STAIRS/VS: Reference Manual. IBM System Manual, 1979.

Google Scholar

[18]

KNUTH, D.E. The Art of Computer Programming. Vol. 3, Sorting and Searching. Addison- Wesley, Reading, Mass., 1973.

Crossref

Google Scholar

[19]

KNUTH, D. E., MORRIS, J. H., AND PRATT, V.R. Fast pattern matching in strings. SIAM J. Comput. 6, 2 (June 1977), 323-350.

Google Scholar

[20]

LARSON, P. A. A method for speeding up text retrieval. In Proceedings of ACM SIGMOD Conference {May), ACM, New York, 1983.

Crossref

Google Scholar

[21]

MCILROY, M.D. Development of a spelling list. IEEE Trans. Commun. COM-30, 1 {Jan. 1982), 91-99.

Google Scholar

[22]

MCLEOD, I.A. A data base management system for document retrieval applications. Inf. Syst. 6, 2 (1981), 131-137.

Google Scholar

[23]

MOOERS, C. Application of random codes to the gathering of statistical information. Bulletin 31, Zator Co., Cambridge, Mass., 1949.

Google Scholar

[24]

PAPOULIS, A. Probability, Random Variables and Stochastic Processes. McGraw-Hill, New York, 1965.

Google Scholar

[25]

PFALTZ, J. L., BERMAN, W. J., AND CAGLEY, E. M. Partial match retrieval using indexed descriptor files. Commun. ACM 23, 9 (Sept. 1980), 522-528.

Crossref

Google Scholar

[26]

RABITTI, F., AND ZIZKA, J. Evaluation of access methods to text documents in office systems. In Proceedings of the 3rd Joint ACM-BCS Symposium on Research and Development in Information Retrieval. 1984.

Crossref

Google Scholar

[27]

ROBERTS, C.S. Partial-match retrieval via the method of superimposed codes. Proc. IEEE 67, 12 (Dec. 1979), 1624-1642.

Google Scholar

[28]

SACKS-DAVIS, R., AND RAMAMOHANARAO, K. A two level superimposed coding scheme for partial match retrieval. Inf. Syst. 8, 4 (1983), 273-280.

Google Scholar

[29]

SALTON, G. The SMART Retrieval System--Experiments in Automatic Document Processing. Prentice-Hall, Englewood Cliffs, N.J., 1971.

Crossref

Google Scholar

[30]

SALTON, G., AND MCGILL, M.J. Introduction to Modern Information Retrieval. McGraw-Hill, New York, 1983.

Crossref

Google Scholar

[31]

SEVERANCE, D. G., AND LOHMAN, G.M. Differential files: their application to the maintenance of large databases. ACM Trans. Database Syst. 1, 3 (Sept. 1976), 256-267.

Crossref

Google Scholar

[32]

STIASSN~, S. Mathematical analysis of various superimposed coding methods. Am. Doc. 11, 2 (Feb. 1960), 155-169.

Google Scholar

[33]

TSICHRITZIS, D., AND CHRISTODOULAKIS, S. Message Files. ACM Trans. Off. Inf. Syst. I, 1 (Jan. 1983), 88-98.

Crossref

Google Scholar

[34]

TSICHRITZIS, D., CHRISTODOULAKIS, S., ECONOMOPOULOS, P., FALOUTSOS, C., LEE, A., LEE, D., VANDENBROEK, J., AND Woo, C. A multimedia office filing system. In Proceedings of the 9th International Conference on Very Large Data Bases, (Oct.-Nov. 1983).

Crossref

Google Scholar

[35]

VAN-RIJSBERGEN, C.J. Information Retrieval. 2nd ed. Butterworths, London, 1979.

Crossref

Google Scholar

Cited By

View all

Meng XZhang XHuo HLeng Q(2024)Top-k approximate selection for typicality query results over spatio-textual dataKnowledge and Information Systems10.1007/s10115-023-02013-266:2(1425-1468)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s10115-023-02013-2
Aggarwal CAggarwal C(2022)Information Retrieval and Search EnginesMachine Learning for Text10.1007/978-3-030-96623-2_9(257-302)Online publication date: 10-Feb-2022
https://doi.org/10.1007/978-3-030-96623-2_9
Wang XMa JMiao YLiu XZhu DDeng R(2021)Fast and Secure Location-Based Services in Smart Cities on Outsourced DataIEEE Internet of Things Journal10.1109/JIOT.2021.30818218:24(17639-17654)Online publication date: 15-Dec-2021
https://doi.org/10.1109/JIOT.2021.3081821
Show More Cited By

Index Terms

Signature files: an access method for documents and its analytical performance evaluation
1. Information systems

Recommendations

Inverted files versus signature files for text indexing

Two well-known indexing methods are inverted files and signature files. We have undertaken a detailed comparison of these two approaches in the context of text indexing, paying particular attention to query evaluation speed and space requirements. We ...
Frame-Sliced Signature Files

A superimposed coding method, frame-sliced signature file, is proposed, and the performance of this method is studied and compared with that of other signature file methods. The response time of the method is improved due to its ability to effectively ...
Declustering of key-based partitioned signature files

Access methods based on signature files can largely benefit from possibilities offered by parallel environments. To this end, an effective declustering strategy that would distribute signatures over a set of parallel independent disks has to be combined ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1984

Published in TOIS Volume 2, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

244
Total Citations
View Citations
2,227
Total Downloads

Downloads (Last 12 months)495
Downloads (Last 6 weeks)28

Reflects downloads up to 24 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Meng XZhang XHuo HLeng Q(2024)Top-k approximate selection for typicality query results over spatio-textual dataKnowledge and Information Systems10.1007/s10115-023-02013-266:2(1425-1468)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s10115-023-02013-2
Aggarwal CAggarwal C(2022)Information Retrieval and Search EnginesMachine Learning for Text10.1007/978-3-030-96623-2_9(257-302)Online publication date: 10-Feb-2022
https://doi.org/10.1007/978-3-030-96623-2_9
Wang XMa JMiao YLiu XZhu DDeng R(2021)Fast and Secure Location-Based Services in Smart Cities on Outsourced DataIEEE Internet of Things Journal10.1109/JIOT.2021.30818218:24(17639-17654)Online publication date: 15-Dec-2021
https://doi.org/10.1109/JIOT.2021.3081821
Chen ZChen LCong GJensen C(2021)Location- and keyword-based querying of geo-textual data: a surveyThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-021-00661-w30:4(603-640)Online publication date: 30-Mar-2021
https://dl.acm.org/doi/10.1007/s00778-021-00661-w
Sanjuan-Contreras CRetamal GMartinez-Prieto MSeco D(2020)cBiK: A Space-Efficient Data Structure for Spatial Keyword QueriesIEEE Access10.1109/ACCESS.2020.29972588(98827-98846)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.2997258
Mahmood AAref W(2019)Scalable Processing of Spatial-Keyword QueriesSynthesis Lectures on Data Management10.2200/S00892ED1V01Y201901DTM05611:1(1-116)Online publication date: 7-Feb-2019
https://doi.org/10.2200/S00892ED1V01Y201901DTM056
Bingmann TBradley PGauger FIqbal Z(2019)COBS: A Compact Bit-Sliced Signature IndexString Processing and Information Retrieval10.1007/978-3-030-32686-9_21(285-303)Online publication date: 7-Oct-2019
https://dl.acm.org/doi/10.1007/978-3-030-32686-9_21
Carlos San JGutierrez RMartinez-Prieto M(2018)A Compact Memory-based Index for Spatial Keyword Query Resolution2018 37th International Conference of the Chilean Computer Science Society (SCCC)10.1109/SCCC.2018.8705231(1-8)Online publication date: Nov-2018
https://doi.org/10.1109/SCCC.2018.8705231
Faloutsos CLee RPlaisant CShneiderman B(2018)Incorporating String Search in a Hypertext System: User Interface and Signature File Design IssuesHypermedia10.1080/09558543.1990.120311822:3(183-200)Online publication date: 29-Oct-2018
https://doi.org/10.1080/09558543.1990.12031182
P. AN. AS. D(2018)Intelligent optimal route recommendation among heterogeneous objects with keywordsComputers & Electrical Engineering10.1016/j.compeleceng.2018.05.00468(526-535)Online publication date: May-2018
https://doi.org/10.1016/j.compeleceng.2018.05.004
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

Inverted files versus signature files for text indexing

Frame-Sliced Signature Files

Declustering of key-based partitioned signature files

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations