共查询到20条相似文献，搜索用时 187 毫秒
1.
Tshering C. Dorji El-sayed Atlam Susumu Yata Mahmoud Rokaya Masao Fuketa Kazuhiro Morita Jun-ichi Aoe 《Information processing & management》2010
Minimal Prefix (MP) double array is an efficient data structure for a trie. However, its space efficiency is degraded by the non-compact management of suffixes. This paper presents three methods to compress the MP double array. The first two methods compress the MP double array by accommodating short suffixes inside the leaf nodes, and pruning leaf nodes corresponding to the end marker symbol. These methods achieve size reduction of up to 20%, making insertion and deletion faster at the same time while maintaining the retrieval time of O(1). The third method eliminates empty spaces in the array that holds suffixes, and improves the maximum size reduction further by about 5% at the cost of increased insertion time. Compared to a Ternary Search Tree, the key retrieval of the compressed MP double array is 50% faster and its size is 3–5 times smaller. 相似文献
2.
3.
《Information processing & management》2001,37(5):741-761
In the information retrieval systems, one of the most important and difficult operations is to extract appropriate keywords from documents. This paper proposes an effective substring search method by extending a pattern matching machine for multi-keyword based on Aho and Corasick (AC) called AC machine. The proposed method enables us to extract keyword candidates as much as possible and to select the suitable keywords for users' purpose at a retrieval stage. This method contains four types of substring search methods (exact, prefix, suffix and proper substring search). This paper also proposes a construction algorithm of the retrieval structure for speeding up the substring search. From the simulation results, it is shown that the retrieval time of the presented method is as fast as the key retrieval method based on the trie. 相似文献
4.
《Information processing & management》2005,41(2):275-288
Many information retrieval systems use the inverted file as indexing structure. The inverted file, however, requires inefficient reorganization when new documents are to be added to an existing collection. Most studies suggest dealing with this problem by sparing free space in an inverted file for incremental updates. In this paper, we propose a run-time statistics-based approach to allocate the spare space. This approach estimates the space requirements in an inverted file using only a little most recent statistical data on space usage and document update request rate. For best indexing speed and space efficiency, the amount of the spare space to be allocated is determined by adaptively balancing the trade-offs between reorganization reduction and space utilization. Experiment results show that the proposed space-sparing approach significantly avoids reorganization in updating an inverted file, and in the meantime, unused free space can be well controlled such that the file access speed is not affected. 相似文献
5.
《Information processing & management》2002,38(2):221-236
We need to access objective information efficiently and arbitrary strings in the text at high speed. In several key retrieval strategies, we often use the binary trie for supporting fast access method in order. Especially, the Patricia trie (Pat tree) is famous as the fastest access method in binary tries, because it has the shallowest tree structure. However, the Pat tree requires many good physician storage spaces in memory, if key set registered is large. Thereby, an expense problem happens when storing this trie to the main storage unit. We already proposed a method that use compact bit stream and compress a Pat tree to solve this problem. This is called Compact Patricia trie (CPat tree). This CPat tree needs capacity of only a very few memory device. However, if a size of key set increases, the time expense that search, update key increases gradually. This paper proposes a new structure of the CPat tree to avoid that it takes much time in search and update about much key set, and a method to construct a new CPat tree dynamically and efficiently. This method divides a CPat tree consisting of bit string to fixed depth. In addition, it compose been divided CPAT tree hierarchically. A construction algorithm that proves this update time requires alteration of only one tree among whole trees that is divided. From experimental result that use 120,000 English substantives and 70,000 Japanese substantives, we prove an update time that is faster more than 40 times than the traditional method. Moreover, a space efficiency of memory increases about 35% only than the traditional method. 相似文献
6.
N.H. Farhat 《Journal of The Franklin Institute》1973,296(6):393-402
The advantages of real-time microwave holography are reviewed. Real-time capabilities require real-time acquisition of the raw hologram data and real-time retrieval of images from the collected data. This paper examines in detail the acquisition of microwave hologram data by double circular scanning of a single reciever in the context of quasi real-time operation. The principle of the double circular scan is presented and the effect of this sampling format on the retrieved image analyzed. Optical bench simulation of hologram recording employing this sampling format is also presented. It is shown that such a scanning format has the attractive properties of economy, speed (?1 holographic frame/sec) and excellent retrieved image quality. Finally, the compatibility of the double circular scan format with scanned transmitter-receiver holography is discussed in the context of practical low-cost systems. 相似文献
7.
8.
In this paper, a new source selection algorithm for uncooperative distributed information retrieval environments is presented. The algorithm functions by modeling each information source as an integral, using the relevance score and the intra-collection position of its sampled documents in reference to a centralized sample index and selects the collections that cover the largest area in the rank-relevance space. Based on the above novel metric, the algorithm explicitly focuses on addressing the two goals of source selection; high-recall, which is important for source recommendation applications and high-precision which is important for distributed information retrieval, aiming to produce a high-precision final merged list. 相似文献
9.
Susumu Yata Masaki OonoAuthor VitaeKazuhiro MoritaAuthor Vitae Masao FuketaAuthor VitaeToru SumitomoAuthor Vitae Jun-ichi AoeAuthor Vitae 《Information processing & management》2007
A trie represented by a double-array enables us to search a key fast with a small space. However, the double-array uses extra space to be updated dynamically. This paper presents a compact structure for a static double-array. The new structure keeps character codes instead of indices in order to compress elements of the double-array. In addition, the new structure unifies common suffixes and consists of less elements than the old structure. Experimental results for English keys show that the new structure reduces space usage of the double-array up to 40%. 相似文献
10.
针对声矢量DOA估计问题,根据声矢量阵的特点,结合MVDR算法的思想,本文提出了一种声矢量阵DOA估计新算法。该算法将声矢量阵振速通道的数据协方差矩阵相加得到新的协方差矩阵,然后结合声矢量阵声压通道的数据协方差矩阵,通过类似于V-MVDR算法的角度扫描过程实现目标的DOA估计,该算法无需已知信源数目且不需要特征值分解运算,具有良好的DOA方位估计和分辨性能,计算机仿真结果验证了本文算法的有效性。 相似文献
11.
Michael J. Nelson 《Information processing & management》1997,33(6):739-744
A prefix trie index (originally called trie hashing) is applied to the problem of providing fast search times, fast load times and fast update properties in a bibliographic or full text retrieval system. For all but the largest dictionaries a single key search in the dictionary under trie hashing takes exactly one disk read. Front compression of search keys is used to enhance performance. Partial combining of the postings into the dictionary is analyzed as a method to give both faster retrieval and improved update properties for the trie hashing inverted file. Statistics are given for a test database consisting of an online catalog at the Graduate School of Library and Information Science Library of the University of Western Ontario. The effect of changing various parameters of prefix tries are tested in this application. 相似文献
12.
A binary approach to data storage and retrieval is introduced. It views the data base as a two-dimensional matrix that relates entities to all possible values the attributes of these entities may take. As such, it provides a unified solution to the two conflicting types of data base transactions—operational and managerial. An analytical investigation of the feasibility of binary storage and a compression method for reducing meaningless areas of the matrix are presented. Storage efficiencies of binary and conventional inverted file methods are compared and evaluated. An analysis of retrieval considerations associated with the binary matrix is given, particularly the issue of going from high to low orders of compression. Results of these analyses indicate that the binary data base's efficiency increases with increases in query complexity. Future research directions are sited and discussed. 相似文献
13.
针对目前3D模型检索速度慢,难以达到实际应用的问题,本文提出了渐进式预检索的思想.首先计算3D模型的质心O,计算模型上各点到质心的距离.该距离反映了模型的几何特征,将距离进行分段统计,得到各段距离的频率分布曲线图,以此为相似性比较条件,可以检索出类似模型,得到初步检索结果.根据最大距离Dmax和最小距离Dmin,建立投影坐标系PCS(Project Coordinate system),分别得到3D模型的3个特征轮廓图,然后采用D2[1]距离进行轮廓图的相似度比较.模型的比较就可以转化成2D图线的比较,这显然降低了模型比较的计算量,大大提高了模型检索的速度.实验结果表明上述算法在模型预检索方面具有突出优点. 相似文献
14.
Vicente P. Guerrero-Bote Felipe Zapico-Alonso María Eugenia Espinosa-Calvo Rocío Gmez Crisstomo Flix de Moya-Anegn 《Information processing & management》2006,42(6):1484
The Pathfinder algorithm is widely used to prune social networks. The pruning maintains the geodesic distances between nodes. It has shown itself to be very useful in the analysis of, amongst others, citations in BIS (bibliometrics, informetrics, and scientometrics). It has even been proposed for the online display of the search results in an information retrieval system. However, its great time and space complexity limits its use in real-time applications and in networks of any considerable size.The present work describes an improved algorithm with considerably reduced time and space complexity. Its lower execution costs thus increase its applicability both in real time and to large networks. 相似文献
15.
A scheme for designing a voice Website-based intelligent WWW information retrieval system is presented.It provides convenient and rapid information retrieval service for more users.Combining the advantages of full-text retrieval and intelligent retrieval,it can improve the response speed,recall ratio and pertinency ratio.Meanwhile,by using ASR,TIS and natural language processing,it can enlarge the scale of Internet users. 相似文献
16.
采用在HSV彩色空间的色调累积直方图和边缘直方图分别表示颜色和形状特征,进行相似性检索,并结合综合权重调整的相关反馈技术来满足用户的检索需求。实验结果表明,此算法能获得有效的检索效果。 相似文献
17.
An algorithm for numerical evaluation of zero order Hankel transform is developed. The method involves one FFT evaluation and a summation of the interpolated FFT components. It compares favorably with other available techniques with regard to speed, accuracy, and ease of usage. 相似文献
18.
《Journal of The Franklin Institute》2023,360(9):6275-6295
As for the multi-agent systems (MASs) with time-varying switching subject to deception attacks, the leader-following consensus problem is studied in this article. The one-sided Lipschitz (OSL) condition is utilized for the nonlinear functions, which makes the results more general and relaxed than those obtained by Lipschitz condition. The nonidentical double event-triggering mechanisms (ETMs) are adopted for only a fraction of agents, and each agent transmits the data according to its own necessity. Semi-Markov process modeling with time-varying switching probability is adopted for switching topology and deception attacks occurring in transmission channel are considered. By using the cumulative distribution function (CDF) and the linear matrix inequality (LMI) technology, sufficient conditions for MASs to achieve consensus in mean square are obtained. An effective algorithm is presented to obtain the event-based control gains. The merits of the proposed control scheme are demonstrated via a simulation example. 相似文献
19.
《Journal of The Franklin Institute》1987,324(3):465-477
A new algorithm for computations of matrix partial fractions representing the inverse of linear matrix pencil is based on an appropriate expression in matrix form of the Pascal triangle. It concerns singular and nonsingular systems and starts with the inverse of regular matrix linear pencil M(s) = sA0 - A where only A0 is singular, or both A0 and A are singular. Nonsingular systems are considered as a particular case of singular systems. The presented algorithm of the matrix partial fraction expansion is suitable to determine the matrix transfer function, and is computer oriented because all manipulations can be performed on matrices with constant entries only. 相似文献