Aggregated 2D range queries on clustered points

Efficient processing of aggregated range queries on two-dimensional grids is a common requirement in information retrieval and data mining systems, for example in Geographic Information Systems and OLAP cubes. We introduce a technique to represent grids supporting aggregated range queries that requires little space when the data points in the grid are clustered, which is common in practice. We show how this general technique can be used to support two important types of aggregated queries, which are ranked range queries and counting range queries. Our experimental evaluation shows that this technique can speed up aggregated queries up to more than an order of magnitude, with a small space overhead.     

Probabilistic location-dependent queries at different location granularities

Approaches for the processing of location-dependent queries usually assume that the location data are expressed precisely, usually using GPS locations. However, this is unrealistic because positioning methods do not have a perfect accuracy (e.g., the positioning approach used in cellular networks handles only the cell where mobile users are located). Besides, users may need to express queries based on concepts of locations other than traditional GPS locations, which we call location granules.In this paper, we focus on location granule-based query processing (i.e., processing of queries with location granules) in situations where the location data available is imprecise, which we have called probabilistic location-dependent queries. For that purpose, we exploit the concept of uncertainty location granule, which represents the location uncertainty of an object. In particular, we tackle the problem of processing probabilistic inside (range) constraints. We analyze in detail how those constraints can be processed, taking into account both the existence of location uncertainty affecting the relevant objects and the location granularity specified. An extensive experimental evaluation shows the feasibility of the proposed probabilistic query processing approach and analyzes the advantages of using index structures to speed up the query processing.     

一种基于数据流驱动的数据流连续查询模型

建立了基于数据流驱动的数据流连续查询模型,介绍了系统结构和解决方案,设计了一些通用的查询算子,并通过查询算子在查询链中的有序组合来构造出各种复杂的连续查询语句。实验表明,该模型可扩充性强,操作简单,适合小规模的数据流查询需要。     

Cache-oblivious index for approximate string matching

This paper revisits the problem of indexing a text for approximate string matching. Specifically, given a text T of length n and a positive integer k, we want to construct an index of T such that for any input pattern P, we can find all its k-error matches in T efficiently. This problem is well-studied in the internal-memory setting. Here, we extend some of these recent results to external-memory solutions, which are also cache-oblivious. Our first index occupies O((nlog^kn)/B) disk pages and finds all k-error matches with O((|P|+occ)/B+log^knloglog_Bn) I/Os, where B denotes the number of words in a disk page. To the best of our knowledge, this index is the first external-memory data structure that does not require Ω(|P|+occ+poly(logn)) I/Os. The second index reduces the space to O((nlogn)/B) disk pages, and the I/O complexity is O((|P|+occ)/B+log^k(k+1)nloglogn).     

外包空间数据库中反向k近邻查询验证

在外包空间数据库模式下,数据持有者委托第三方数据发布者代替它来管理数据并且执行查询.当发布者受到攻击或者由于自身的不安全性,它可能返回不正确的查询结果给用户.基于已有的反向k近邻(ReversekNearest Neighbor,RkNN)查询方法,采用将反向k近邻查询验证转化成k近邻查询验证和范围查询验证的思想,提出一种反向k近邻查询验证的方法,并且设计了相应的算法,用于验证返回给客户端结果的正确性(没有结果点被篡改),有效性(结果点都满足用户的查询要求)和完整性(没有遗漏符合查询要求的结果点).实验验证了算法的有效性和实用性.     

Evaluation of aluminium/alumina/titanium composites produced by continual annealing and roll-bonding process

Anodising, continual annealing and roll-bonding (CAR) processes were employed to fabricate aluminium/alumina/titanium composites with different amounts of alumina. After each rolling cycle, annealing treatment was performed at 300°C for 1?h. After six cycles of CAR process, the Al/0.22 vol.-% Al₂O₃/13vol.-%Ti composite showed uniform alumina and titanium particles distribution. The tensile strength of the composites first decreased after the first cycle, then increased up to 200?MPa after the sixth cycle. Conversely, by increasing the alumina content (Al/0.43vol.-%Al₂O₃/13vol.-%Ti composite), microhardness and tensile strength immediately increased. SEM micrographs demonstrated that by increasing the number of cycles, the dimples density increased from 0.007 to 0.028?µm^?2 for the first and the last cycles, respectively.     

Music in the home: Interfaces for music appliances

The development of networked information appliances, combined with the proliferation of broadband Internet access and e-commerce, has the potential to greatly affect media consumption in the home. In this paper we consider the influence of these developments on a common domestic activity, finding and listening to music. After summarising the relative strengths and weaknesses of accessing music in physical and digital formats, we present a design concept which is intended to combine the advantages of the old and new media. In particular, we focus on the problem of visual information seeking within the context of music and touchable screen displays.     

Approximate all nearest neighbor search for high dimensional entropy estimation for image registration

Information theoretic criteria such as mutual information are often used as similarity measures for inter-modality image registration. For better performance, it is useful to consider vector-valued pixel features. However, this leads to the task of estimating entropy in medium to high dimensional spaces, for which standard histogram entropy estimator is not usable. We have therefore previously proposed to use a nearest neighbor-based Kozachenko-Leonenko (KL) entropy estimator.Here we address the issue of determining a suitable all nearest neighbor (NN) search algorithm for this relatively specific task.We evaluate several well-known state-of-the-art standard algorithms based on k-d trees (FLANN), balanced box decomposition (BBD) trees (ANN), and locality sensitive hashing (LSH), using publicly available implementations. In addition, we present our own method, which is based on k-d trees with several enhancements and is tailored for this particular application.We conclude that all tree-based methods perform acceptably well, with our method being the fastest and most suitable for the all-NN search task needed by the KL estimator on image data, while the ANN and especially FLANN methods being most often the fastest on other types of data. On the other hand, LSH is found the least suitable, with the brute force search being the slowest.     

基于ALS抑制剂药效团模型的数据库搜索

以ALS抑制剂药效团模型为基础建立了提问结构,将药效团模型中的生物结构信息输入到多种小分子三维结构数据库中(NCI-3D和ACD-3D数据库),借助分子三维结构搜索软件(3DFS和ISIS/3D软件)和多种搜索方法(POW-ELL方法和遗传算法)分别搜寻出100多个符合特征结构信息的全新结构候选化合物。这些命中结构的分子特征信息为我们下一步进行分子设计,确定先导化合物结构明确了方向,并提供了重要依据。