一种基于关键词搜索的空间连接查询

许多实际的应用需要同时支持空间连接查询和关键词搜索。在给出基于关键词的空间连接（KSJ）查询定义的基础上,对参与KSJ查询的空间数据集建立MIR2-树索引结构,并结合一些高效的搜索剪枝策略,提出一种基于宽度优先的KSJ查询算法。实验结果表明该算法可有效支持基于关键词的空间连接查询处理。     

空间查询和路径搜索的集成处理策略

在数据库研究中,路径搜索和空间查询处理被认为是两个互不相关的领域,然而在处理具有空间约束的路径查询时,需要数据库系统提供路径计算和空间查询处理两方面的功能.为了处理路径计算中的空间约束,考虑了两类处理策略:(1) 空间运算是否在路径计算之前预处理;(2) 空间对象是否在路径计算之前预选取.基于这两类策略,应用现有的空间连接、R-树空间搜索和空间对象聚类技术,提出4种集成的空间路径查询处理方法.     

面向GML的渐进式合并空间连接查询

在面向地理数据服务的空间数据集成系统中,常常需要对由地理数据服务动态生成的GML做进一步的空间连接查询处理才能得到用户最终的查询结果.研究并提出了一种面向GML的渐进式合并空间连接查询处理算法PrMSJ,其主要思想是改造传统基于划分的空间合并连接算法,使之能够以渐进的方式处理面向GML的空间连接查询;提出了一种基于驻留度的动态同步替换策略(DCFP)处理内存溢出;还提出了一种基于完备参考点的方法进行冗余结果检测.实验结果表明,所提出算法优于现有的渐进式空间连接查询处理算法.     

基于对象集合的空间关键词查询

在进行空间关键词查询时,有时需要查找一组既紧凑且离查询点最近、又覆盖查询关键词且对象个数很少的对象,而现有的查询方法通常只能返回包含所有查询关键词的单个空间对象。为此,提出了解决此类查询问题的近似查询算法和精确查询算法。首先给出了这类查询问题的形式化定义,以及描述对象集合质量的代价函数,并对代价函数进行了归一化处理;然后在近似查询算法中采用基于IR-tree的最佳优先搜索策略进行剪枝,有效缩减了查询候选空间;在精确查询算法中采用基于IR-tree的广度优先搜索策略查找包含查询关键词的对象,以达到降低查询处理代价的目的。实验结果表明,近似算法的查询效率明显优于精确算法,且能获得非常精确的查询结果。     

空间关键词搜索研究综述

由于越来越多的数据具有位置和文本双重属性,空间关键词查询(spatial keyword query,简称SKQ)应运而生.一个SKQ以一个地理位置和若干关键词作为参数,返回满足空间与文本约束的结果,这些结果往往根据指定公式排列.对现有的空间关键词搜索技术进行了梳理,首先对问题进行了描述,对挑战进行了分析;然后分析了基本空间关键词搜索技术.将文献中提出的各种空间关键词查询进行了划分,对现有的查询处理技术进行分类,对每种类型的技术,从索引技术和查询算法两个方面进行了总结,并从多个角度对它们进行了比较.其后介绍了扩展空间关键词搜索技术,还介绍了与该问题相关的其他研究工作.最后指出了研究中存在的不足以及以后的研究方向.     

基于R树的方向关系查询处理

方向关系描述了对象间的空间顺序关系.近年来,方向关系查询处理逐渐受到空间数据挖掘和地理信息系统等空间数据库应用领域研究者的关注.方向关系查询处理需要执行方向连接操作,目前有关空间连接的研究主要集中在拓扑关系和距离关系方面,而较少考虑方向关系.研究了基于R树的方向关系查询处理方法,定义了四元组模型表示对象MBR间的方向关系,提出了基于R树的处理方向关系查询过滤(filter)步骤的方法,并将提炼(refinement)步骤细化为3种不同的操作.所提出的方法能够高效处理任意对象间的方向关系查询.考虑到空间数据挖掘中方向关系查询通常是在满足一定距离约束条件的对象之间进行,还提出了一种同时利用方向和距离约束限制R树搜索空间的查询处理算法.实验证明,与不利用R树的方向关系查询处理方法相比,所提出的方法在I/O开销和CPU开销两方面都具有很高的性能.     

一种面向大规模空间文本数据的空间结构匹配算法

为了支持各类基于位置的服务,人们提出了各种查询和搜索空间文本数据的方法和技术.传统的空间关键字查询和近期提出的空间模式匹配不支持用户定义查询关键字对象以及对象之间细致的空间结构关系,使得查询结果集庞大但无效结果偏多,不能满足用户高效且精确的查询需求.本文因此提出了一种新的查询模式——空间结构匹配查询(Spatial Structure Matching,SSM),允许用户定义一组查询关键字对象并指定任意两个对象之间的距离和方向约束.为了解决SSM查询问题,本文首先提出了一种基于多路连接的基准方法,将SSM查询问题分解为单个对象的关键字匹配,两个对象的边匹配和多个对象的聚合匹配.为了提高SSM查询效率,本文提出了基于扫描线算法的边匹配计算,利用对象的地理位置信息来降低边匹配计算开销.本文利用同时满足查询关键字,距离和方向约束的空间对象构造对象连接图,从而将SSM查询问题转换为在对象连接图上搜索与SSM查询结构同构的子图匹配问题,并且利用经典的子图同构匹配算法求解获得最终的查询结果.在四个大规模空间文本数据集上的实验结果表明,本文所提算法的查询效率远高于对比算法,返回的查询结果集精简有效且...     

一种支持联合搜索的多用户动态对称可搜索加密方案

近年来,满足前后向安全的动态对称可搜索加密(dynamic symmetric searchable encryption, DSSE)一直备受关注,它可以抵抗文件注入攻击,同时限制服务器学习已删除文档的相关信息.不过大多数满足前后向安全的DSSE方案仅支持单关键词搜索,Patranabis等人在NDSS 2021会议上提出了一种支持联合搜索且满足前后向安全的动态可搜索加密方案,但该方案在某些情况下不能得到准确的查询结果,同时不能支持多用户查询.针对以上问题,通过改进不经意交叉索引(oblivious cross tags, OXT)协议,提出了一种支持联合搜索的多用户动态对称可搜索加密方案.该方案利用有限域中元素具有乘法逆元的性质,引入了一次性盲因子,并结合数字信封技术实现了多客户端查询的功能.方案分析与实验表明,所提方案满足了前向安全与后向安全,不仅可以提供准确的联合查询功能,而且支持多客户端查询,同时计算效率仅与更新次数最低的关键词更新次数有关．     

度量空间中的Top-k反向Skyline查询算法

不同于传统的度量空间Skyline查询,提出了一种新颖的度量空间中的Skyline查询MkRS(metric top-kreverse skyline).MkRS从反向角度执行度量空间中的Skyline.给定查询对象q和单调参考函数f,MkRS返回k个包含m个数据对象的子集,以至于每个子集G的度量Skyline包含q.评估这种查询,需要执行从输入数据集P中n个数据对象里选择m个对象的穷举搜索以及每个排列子集的度量Skyline.这些计算由于巨大的搜索空间而需要极高成本.提出了基于排序机理的算法STS(sort and threshold skyline),它可以提前终止计算,仅需要检查很少部分的子集.然后,利用信息重用技术给出了基于重用的STS算法rSTS(reuse STS),进一步减少了STS中80%以上的I?O访问.大量的实验表明提出的算法有效、快速.     

路网中移动对象快照K近邻查询处理

扩展了一种支持路网中移动对象的位置相关查询框架的功能,利用存在磁盘上的R树来存储网络连通性和一种基于内存的网格结构来维持移动对象的位置更新,提出了基于范围查询(MNDR)的快照K近邻查询算法(SKNN),对空间中的任意一条边,分析可能受影响的最大数量和最小数量的网格单元格,说明用于快照范围查询处理的搜索空间的最大范围,预估包含查询结果的子空间,使用这个子空间作为范围调用MNDR来有效地计算路网中查询点的KNN POI,降低I/O成本,缩短查询时间。通过实验对比,当规模扩展到数十万的移动对象时,SKNN比种有效查询处理空间网络数据的预计算方法S-GRID有更好大的系统吞吐量。     

Integrating bilingual search results for automatic junk image filtering

Keyword-based image search engines are now very popular for accessing large amounts of Web images on the Internet. Most existing keyword-based image search engines may return large amounts of junk images (which are irrelevant to the given query word), because the text terms that are loosely associated with the Web images are also used for image indexing. The objective of the proposed work is to effectively filter out the junk images from image search results. Therefore, bilingual image search results for the same keyword-based query are integrated to identify the clusters of the junk images and the clusters of the relevant images. Within relevant image clusters, the results are further refined by removing the duplications under a coarse-to-fine structure. Experiments for a large number of bilingual keyword-based queries (5,000 query words) are simultaneously performed on two keyword-based image search engines (Google Images in English and Baidu Images in Chinese), and our experimental results have shown that integrating bilingual image search results can filter out the junk images effectively.     

Ontology based user query interpretation for semantic multimedia contents retrieval

Users who are familiar with the existing keyword-based search have problems of not being able to configure the formal query because they don’t have generic knowledge on knowledge base when using the semantic-based retrieval system. User wants the search results which are more accurate and match the user’s search intents with the existing keyword-based search and the same search keyword without the need to recognize what technology the currently used retrieval system is based on to provide the search results. In order to do the semantic analysis of the ambiguous search keyword entered by users who are familiar with the existing keyword-based search, ontological knowledge base constructed based on refined meta-data is necessary, and the keyword semantic analysis technique which reflects user’s search intents from the well-established knowledge base and can generate accurate search results is necessary. In this paper, therefore, by limiting the knowledge base construction to multimedia contents meta-data, the applicable prototype has been implemented and its performance in the same environment as Smart TV has been evaluated. Semantic analysis of user’s search keyword is done, evaluated and recommended through the proposed ontological knowledge base framework so that accurate search results that match user’s search intents can be provided.     

Using visual spatial search interface for WWW applications

Most Internet search engines are keyword-based. They are not efficient for the queries where geographical location is important, such as finding hotels within an area or close to a place of interest. A natural interface for spatial searching is a map, which can be used not only to display locations of search results but also to assist forming search conditions. A map-based search engine requires a well-designed visual interface that is intuitive to use yet flexible and expressive enough to support various types of spatial queries as well as aspatial queries. Similar to hyperlinks for text and images in an HTML page, spatial objects in a map should support hyperlinks. Such an interface needs to be scalable with the size of the geographical regions and the number of websites it covers. In spite of handling typically a very large amount of spatial data, a map-based search interface should meet the expectation of fast response time for interactive applications. In this paper we discuss general requirements and the design for a new map-based web search interface, focusing on integration with the WWW and visual spatial query interface. A number of current and future research issues are discussed, and a prototype for the University of Queensland is presented.     

Graph-based retrieval of building information models for supporting the early design stages

Building information modeling (BIM) principles are transforming today’s communication and working processes in the field of construction, however the early design phases are only rarely supported and information technology is therefore not exploited to its full potential. The early design phases are characterized by an iterative process of searching for plausible solutions. A common approach is to refer to similar examples, which are conventionally found using keyword-based search strategies.To this end we propose a method for indexing spatial configurations along with a sketch-based input method for search strategies that uses so-called semantic fingerprints of buildings. The topology of spatial configurations is extracted from building information models and represented as graphs. For both building information models and the user sketches, the extracted graphs are used as the basis for a subgraph-matching algorithm facilitating an intuitive novel query method for researching similar reference examples. The system is able to present corresponding existing solutions to even rudimentary sketches or fragments of a design idea. In addition to graph matching and sketch-based interaction, more recent BIM-based approaches are also taken into account.     

Integration of document index with perception index

 We propose the perception index (PI) that contains attributes associated with a focal keyword restricted by fuzzy term(s) used in fuzzy queries on the Internet. The PI assists the user to reflect his/her perception in the process of query. If we integrate the document index (DI) used in commercial Web search engines with the proposed PI, we can handle both crisp terms (keyword-based) and fuzzy terms (perception-based). In this respect, the proposed approach is softer than the keyword-based approach. The PI brings somewhat closer to natural language. It is a further step toward a real human-friendly, natural language-based interface for Internet. It should greatly help the user relatively easily retrieve relevant information.     

TMS: A free-form text-management system

TMS (Text Management System) is a database management system that supports an access method based on both select and search queries. TMS provides support for variable-length records with pointer fields within the relation. Pointers can be used to support not only text but data from any media, such as graphics and images. An inverted index based on the variable-length record structure is used for speedy retrieval of records based on keywords. In this paper, the variable length record management of TMS and the keyword-based retrieval mechanism are described.     

Context-based literature digital collection search

We identify two issues with searching literature digital collections within digital libraries: (a) there are no effective paper-scoring and ranking mechanisms. Without a scoring and ranking system, users are often forced to scan a large and diverse set of publications listed as search results and potentially miss the important ones. (b) Topic diffusion is a common problem: publications returned by a keyword-based search query often fall into multiple topic areas, not all of which are of interest to users. This paper proposes a new literature digital collection search paradigm that effectively ranks search outputs, while controlling the diversity of keyword-based search query output topics. Our approach is as follows. First, during pre-querying, publications are assigned into pre-specified ontology-based contexts, and query-independent context scores are attached to papers with respect to the assigned contexts. When a query is posed, relevant contexts are selected, search is performed within the selected contexts, context scores of publications are revised into relevancy scores with respect to the query at hand and the context that they are in, and query outputs are ranked within each relevant context. This way, we (1) minimize query output topic diversity, (2) reduce query output size, (3) decrease user time spent scanning query results, and (4) increase query output ranking accuracy. Using genomics-oriented PubMed publications as the testbed and Gene Ontology terms as contexts, our experiments indicate that the proposed context-based search approach produces search results with up to 50% higher precision, and reduces the query output size by up to 70%.