A scalable constraint-based Q-hash indexing for moving objects

In this paper, we develop a Q-hash index structure to efficiently store the position of moving objects. An environment of moving objects contains continuously changing locations which are hard to index using traditional index structures such as R-trees, QuadTrees and their variants. In order to answer the queries accurately, one of the problems faced in storing these positions is the number of updates that have to be made to the database whenever locations change. The high maintenance overhead on updates leads to performance degradation of these index structures; additionally, it makes the database very bulky which results in very poor performance in terms of query execution time. One of the main objectives of the structure we propose is to minimize the number of updates to the database to an optimal number so that the accuracy and response time of the query result are not compromised and at the same time the number of wireless communications can be reduced. The indexing is done using a hashing technique where the hashing function makes use of a region based QuadTree structure. To improve the efficiency of the query processing our index structure helps us define constraints over speed, direction and location of the moving object at the device level which controls the number of updates. In addition, in order to answer different query types efficiently at all levels we propose a three-tier (moving object, regional server, central repository) architecture. Our extensive performance evaluation and comparison of the proposed technique concludes that our scheme outperforms existing Q + R-tree and QuadTree in terms of range query execution time by a high order of magnitude.     

iSAX: disk-aware mining and indexing of massive time series datasets

Current research in indexing and mining time series data has produced many interesting algorithms and representations. However, the algorithms and the size of data considered have generally not been representative of the increasingly massive datasets encountered in science, engineering, and business domains. In this work, we introduce a novel multi-resolution symbolic representation which can be used to index datasets which are several orders of magnitude larger than anything else considered in the literature. To demonstrate the utility of this representation, we constructed a simple tree-based index structure which facilitates fast exact search and orders of magnitude faster, approximate search. For example, with a database of one-hundred million time series, the approximate search can retrieve high quality nearest neighbors in slightly over a second, whereas a sequential scan would take tens of minutes. Our experimental evaluation demonstrates that our representation allows index performance to scale well with increasing dataset sizes. Additionally, we provide analysis concerning parameter sensitivity, approximate search effectiveness, and lower bound comparisons between time series representations in a bit constrained environment. We further show how to exploit the combination of both exact and approximate search as sub-routines in data mining algorithms, allowing for the exact mining of truly massive real world datasets, containing tens of millions of time series.     

基于LSI的代码-文档可追溯关联挖掘研究

软件过程产品间可追溯关联挖掘对软件维护及需求跟踪等众多领域至关重要。基于此,提出一种基于潜在语义索引提取程序代码和中文文档关联信息的方法,该方法是对向量空间模型的改进,通过分析文本间隐含的语义结构来确定关联度,而不依赖于词项的匹配。实验结果表明,该方法不依赖于代码和文档预先定义的同义词库和知识库,并能一定程度上提高查全率和查准率。     

一种大规模数据的快速潜在语义索引

潜在语义索引（LSI）已应用到现代信息检索的多个领域,但矩阵奇异值分解的高复杂度阻碍了该技术在大规模数据上的应用。提出一种大规模数据的快速LSI方法。给出一个降维问题的统一框架,LSI作为一种特征提取算法,可以在这个框架下转化为一个特征选择问题。利用该技术在最大程度保持LSI降维效果的同时,简化LSI的计算,使其能够应用于大规模数据。     

基于非负矩阵分解的中文文本主题分类

提出基于非负矩阵分解（NMF）的中文文本主题分类方法,应用NMF算法分解词．文本矩阵获取词之间的相关性,有效地解决同义词、多义词的影响。实验结果表明,与基于奇异值分解的潜在语义索引方法相比,该方法计算速度快、占用存储空间较少。在潜在语义数据降低较大的情况下,NMF方法具有更好的分类精度。     

The study of indexing techniques on object oriented databases

An object-oriented database (OODB) has been becoming more important in recent years. It can deal with a large amount of complex objects and relationships that relational database (RDB) systems cannot handle well. However, the retrieval and update performance of an OODB depends on indexing techniques. In this paper, we study the indexing techniques on OODBs, based on an inheritance hierarchy and an aggregation hierarchy. Given the access probability and the size of each class, we propose a cost function to evaluate the gain of building an index on an inheritance hierarchy. For an aggregation hierarchy, we use a path-catenation technique to evaluate how to build index files on classes. Through some experiments, we found our methods have better retrieval performance than most ones proposed before.     

互补网络中多级混合过滤系统的研究

针对适合互补结构网络信息特点的过滤机制进行研究,提出一种改进的用户兴趣模型,在研究内容过滤和协作过滤的基础上．建立适合互补结构网络的多级混合过滤系统。通过对多级混合过滤模型的实验,表明多级混合过滤模型克服了单独使用内容过滤或协作过滤方法的缺点,提高了过滤的准确度。     

Correlating burst events on streaming stock market data

We address the problem of monitoring and identification of correlated burst patterns in multi-stream time series databases. We follow a two-step methodology: first we identify the burst sections in our data and subsequently we store them for easy retrieval in an efficient in-memory index. The burst detection scheme imposes a variable threshold on the examined data and takes advantage of the skewed distribution that is typically encountered in many applications. The detected bursts are compacted into burst intervals and stored in an interval index. The index facilitates the identification of correlated bursts by performing very efficient overlap operations on the stored burst regions. We present the merits of the proposed indexing scheme through a thorough analysis of its complexity. We also manifest the real-time response of our burst indexing technique, and demonstrate the usefulness of the approach for correlating surprising volume trading events using historical stock data of the NY stock exchange. While the focus of this work is on financial data, the proposed methods and data-structures can find applications for anomaly or novelty detection in telecommunication, network traffic and medical data.     

Audio indexing: primary components retrieval

This work addresses the soundtrack indexing of multimedia documents. Our purpose is to detect and locate sound unity to structure the audio dataflow in program broadcasts (reports). We present two audio classification tools that we have developed. The first one, a speech music classification tool, is based on three original features: entropy modulation, stationary segment duration (with a Forward–Backward Divergence algorithm) and number of segments. They are merged with the classical 4 Hz modulation energy. It is divided into two classifications (speech/non-speech and music/non-music) and provides more than 90% of accuracy for speech detection and 89% for music detection. The other system, a jingle identification tool, uses an Euclidean distance in the spectral domain to index the audio data flow. Results show that is efficient: among 132 jingles to recognize, we have detected 130. Systems are tested on TV and radio corpora (more than 10 h). They are simple, robust and can be improved on every corpus without training or adaptation.

基于数据空间网格划分的PK 树索引结构*

在大规模高维数据挖掘研究中,数据存储与索引方法的有效性是决定算法时空效率的重要因素。将数据空间网格划分策略与高效率的树型索引结构结合起来,可以充分发挥两者在数据组织上的综合优势,将复杂问题转换为结构化的简单重复问题。在统一的框架下给出了各种数据空间网格划分的定义,讨论了两种适用于实现网格化数据索引的R树和PK树索引结构。试验结果表明,PK树在数据存储和索引上具有更高的效率,与网格化数据组织方法结合起来,对于降低大规模高维数据分析问题的时空复杂度具有重要意义。