Query by Impression: A Novel Place Query System with Adjacency Constraints

在我們的日常生活中常會遇到搜尋地點的需求，並且在不同的場合下使用者 會有不同的地點搜尋模式。其中一種常見的需求為找尋一個地點的確切位置，例 如，搜尋台北101 的確切位置與地址；另一種基本的搜尋需求是希望在地圖上標 出某個區域內的特定種類地點，例如，搜尋台灣大學附近的所有日式餐廳。然而， 根據我們的觀察，還有一種地點搜尋的需求也時常出現在我們的生活中。當我們 想要推薦一個曾經去過的地點給朋友時，也許忘記所欲推薦地點的確切名稱。而 使用者憑藉印象仍記得某些資訊，其中包含了此地點的類別、所在的大略區域、 以及此地點周圍的一些明顯標地。例如，想推薦一個上個月去過位在台北市東區 的日式餐廳給朋友，但卻無法想起確切的餐廳名稱，但是知道其附近有公園及超 級市場。 為了解決這樣的問題，我們提出了一個基於使用者過往印象之新穎地點搜尋 技術。我們設計了兩種演算法，分別為"離線距離增強演算法"及"空間索引增強演 算法"。演算法的主要目的為能夠正確且即時地回覆使用者的搜尋。再者，透過使 用者搜尋後的回饋資訊，我們提出改善機制以提高系統之準確率。為了驗證所提 出方法之正確性與效能，我們實作了基於過往印象之地點搜尋系統。此系統包含 了超過四萬筆地點資訊之真實城市資料庫。藉由實際使用者的測試與實驗分析， 我們驗證了所提出系統具備高準確率，且符合此應用之即時搜尋需求。In our daily life, place query is one of the most fundamental applications. Traditional use cases include finding the exact spatial location of a place and searching for a specific type of places in a given spatial range. On the other hand, there is another possibility that you may want to recommend a visited place to friends but forget the complete name of the place. You have vague impressions on it and only remember the information of the place type, the rough range of the place, and some places near it. For example, a user may want to find a Japanese food restaurant which is located in the eastern part of a city, and there are a park and a supermarket adjacent to this restaurant. To enable the capability of query by impression that has not been fully explored in the literature, in this paper, we define a new place query problem called Place Query with Adjacency Constraints (abbreviated as PQAC). We propose a naive approach and two enhancement algorithms, distance pre-calculating algorithm and grid indexing algorithm, to achieve greater efficiency that can satisfy the real-time need of this place query service. Furthermore, we also consider using user query feedback to increase the accuracy of the results. We implement a Query By Impression (abbreviated as QBI) system with a real metropolitan place dataset consisting of more than 40,000 place records from Google Place API. Experiments with user study collected from 15 volunteers are conducted to validate the efficiency and effectiveness of the proposed QBI system