On the cost of searching signature trees

被引：2

作者：

Chen, YJ ^{[1
]}

机构：

[1] Univ Winnipeg, Dept Appl Comp Sci, Winnipeg, MB R3B 2E9, Canada

来源：

INFORMATION PROCESSING LETTERS | 2006年 / 99卷 / 01期

基金：

加拿大自然科学与工程研究理事会;

关键词：

data structures; index; signature files; signature identifiers; signature trees; probabilistic analysis; contour integration;

D O I：

10.1016/j.ipl.2005.10.015

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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 detailed study of probabilistic analysis in conjunction with suitable contour integration of complex variabled functions. (c) 2006 Elsevier B.V All rights reserved.

引用

页码：19 / 26

页数：8

共 16 条

[1] Querying documents in object databases [J].

Abiteboul S. ;

Cluet S. ;

Christophides V. ;

Milo T. ;

Moerkotte G. ;

Siméon J. .

International Journal on Digital Libraries, 1997, 1 (1) :5-19

[2]

Aho A.V., 1974, The Design and Analysis of Computer Algorithms

[3]

[Anonymous], 1973, ART COMPUTER PROGRAM

[4]

Chang W. W., 1989, Proceedings of the Fifteenth International Conference on Very Large Data Bases, P145

[5] Signature files and signature trees [J].

Chen, YJ .

INFORMATION PROCESSING LETTERS, 2002, 82 (04) :213-221

[6] DESIGN CONSIDERATIONS FOR A MESSAGE FILE SERVER [J].

CHRISTODOULAKIS, S ;

FALOUTSOS, C .

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 1984, 10 (02) :201-210

[7]

CHURCHILL RV, 1958, OPERATIONAL MATH

[8] Declustering of key-based partitioned signature files [J].

Ciaccia, P ;

Tiberio, P ;

Zezula, P .

ACM TRANSACTIONS ON DATABASE SYSTEMS, 1996, 21 (03) :295-338

[9] Comparison of signature file models with superimposed coding [J].

Dervos, D ;

Manolopoulos, Y ;

Linardis, P .

INFORMATION PROCESSING LETTERS, 1998, 65 (02) :101-106

[10]

Faloutsos C., 1990, Hypermedia, V2, P183

← 1 2 →