情報処理学会 インタラクション 2016
IPSJ Interaction 2016

162C502016/3/3

Route Recommendation System by Extracting
Popular and Visible Landmarks
Shoko Wakamiya1,a) Hiroki Morinaga2,b) Tomoki Taniyama2,c)Kaisei Waki2,d) Adam Jatowt3,e) Yukiko Kawai4,f) Toyokazu Akiyama4,g)Hiroshi Kawasaki2,h)Abstract: In this paper, we define three types of landmarks according to their properties, “point landmarks”,“linear landmarks”, and “area landmarks,” those are not only visually distinguishable, but also easily noticeable based on human perception. Such landmarks are eﬃciently retrieved by analyzing microblogs. By
exploiting the unique feature of those three types of landmarks, our navigation system can generate route
directions, which is easy to remember and helpful for users to self-localize their position without heavily
depending on their smart phones. In the experiment, we tested the system with virtual environment andconfirmed that users of our system could reach the destination using a small number of landmarks, whichmeans users need to check screens less than other system.
Keywords: Popularity, visibility, route recommendation, microblog, check-in, location-based SNS

1.

Introduction

Although various route navigation systems have been developed so far, majority of the existing systems tend to provide eﬃcient routes in terms of distance or time required
to reach destinations. However, in reality, the route instructions given by automatic systems and those by humans tend
to be diﬀerent: e.g., the former usually output instructions
with street names used as reorientations, while the latteroften use landmarks rather than street names [1]. Due tothis mismatch, when following route directions suggested byautomatic systems, users have to check the directions multiple times, resulting in eyeballing maps on small screens of
their handheld devices. This not only makes the orienteering and way-finding diﬃcult, but it also leads to concernsof safety while walking or cycling. Further, the systems
cannot be used in case when GPS and/or digital map information are not available (e.g., when travelling abroad).
As a solution, a small number of instructions, especially byusing landmarks, required for navigation is preferred, as being easy to be memorized and requiring low count of map
1234a)
b)
c)
d)e)
f)
g)
h)

Nara Institute of Science and Technology
Kagoshima University
Kyoto University
Kyoto Sangyo University
shokow@cc.kyoto-su.ac.jp
sc110080@ibe.kagoshima-u.ac.jp
sc110042@ibe.kagoshima-u.ac.jp
sc115087@ibe.kagoshima-u.ac.jp
adam@dl.kuis.kyoto-u.ac.jp
kawai@cc.kyoto-su.ac.jp
akiyama@cc.kyoto-su.ac.jp
kawasaki@ibe.kagoshima-u.ac.jp© 2016 Information Processing Society of Japan

Fig. 1: Overview of useful landmarks.

references [2], [4], [6].
It should be noted that using landmarks is not only eﬀective to instruct the route direction, but also helpful for users
to self-localize their position; this is realized because landmarks increase users’ spatial awareness by informing them
about surroundings and decreasing eﬀort required for constructing the mental representation of unfamiliar cities.
In the previous work, we propose an automatic system toeﬃciently generate memorable route using a small numberof landmarks [6]. This is realized by introducing the threetypes of landmarks as shown in Fig. 1. Although the landmarks are only extracted based on visibility in the previous
work, we further introduce human perception to extract thelandmarks in the paper as follows:
Point landmark (Local landmark) is characterized
by rather poor visibility, their relatively high visit

683

情報処理学会 インタラクション 2016
IPSJ Interaction 2016

popularity within local areas facilitates their discovery(e.g., post oﬃce, restaurant, or library). Navigating
users are expected to identify their locations accurately
when having received a route recommendation withpoint landmarks. (e.g., “Go straight and turn right atthe post oﬃce.”)Line landmark is a continuous line connecting multiple intersections such as main streets, highways, rivers,and railways. In the work, we further consider
crowded streets as line landmarks. Note thatsince line landmarks are characterized by 1D ambiguity
along a route, they were not commonly used as landmarks.
Area landmark (Global landmark) A tall and distinctive structure can be recognized from far away. In
addition, we regard an area landmark to begathering considerable crowd’s attention evenfrom users who are at diﬀerent locations andcannot directly see the landmarks. Such places
are characterized by their relatively high visit
popularity and high indirect visibility as well.
“Walk toward the red tower.” is an example of a route
recommendation with an area landmark with previous
technique and “toward the center of downtown”
is an example of new one.
Based on the extracted landmarks we construct a routegraph which facilitates optimal route search in terms of thenumber of landmarks as well as distance. We demonstrate
an online route recommendation system [3] for San Francisco, Kagoshima and Kyoto cities.

2.

Extracting Useful Landmarks

2.1 Measuring Visit Popularity of PlacesFirst, popular places are extracted by measuring visit popularity for each place. Although there are several places
characterized by many checkins, some of the checkins arerepeatedly made by the same users (e.g., owners of theseplaces). We assume that the higher the number of uniqueusers checked in at a place (users) is, the more popular theplace is. Thus, we use then the number of users, users,
checked in each place as the visit popularity of the place.
Popular places whose visit popularity is over the value of a
fixed threshold, these places are extracted as candidates ofpoint and area landmarks. The way to compute their visibilities (direct/indirect) will be explained in the following
sections.
2.2 Measuring Indirect Visibility of Places
Next, we compute indirect visibility for detected popular places. Famous places can be regarded useful landmarks
and are often used for route navigation in the real world.
Our approach relies on comparing the locations of users
who mentioned a place in their tweets with the locationsof places. This would indicate actually popular places thatpeople talk about even without visiting them or before/aftervisiting them. The intuition behind this choice is that such

© 2016 Information Processing Society of Japan

162C502016/3/3

places should have several clues enabling users to find theway to reach them, even if the users cannot directly seethem. For instance, ‘Kinkaku-ji Temple (Golden pavilion)’in Kyoto city, Japan cannot be seen from distant, but one
can find various road signs at intersections that show directions to it, several buses bound for it and many related advertisements. As other examples, signs and advertisementsof a shop will be explicit clues and people having a shop’s
original shopping bag can be regarded as an implicit clue.
Based on this reasoning, we define indirect visibility as
the second indicator of the landmark’s utility. In fact, thisindicator is related to the concept of collective spatial attention [5] defined as the geographic area of interest andfocus of multiple users. In this paper, our assumption isthat popular places are typically mentioned by users who
are nearby there. On the other hand, truly popular places
are also referred by users at other distant locations.
We calculate location diﬀerence as the Euclidean distance
between the coordinates of place of a tweet and the coordinates of intersection of the tweet. If the average value oflocation diﬀerences for a place is high, we can regard theplace is indirectly recognizable from distant intersections.
2.3 Measuring Direct Visibility of Places
The third indicator for determining landmark’s utility, direct visibility, is measured by analyzing 3D geographic data.
In particular, high-rise buildings and towers which are seenfrom within larger areas can be detected based on this measure.
We use a map involving 3D shape information of all buildings in a city with 3D computer graphics (3DCG). Popularplaces are assigned to buildings based on their coordinates.
In addition, top n tallest buildings are selected from allbuildings in each block, which is set by dividing a target
city into blocks, each of m km2 size. Thus, we measure
direct visibility of a place.
2.4

Classifying Places into Point and Area Landmarks
We describe here how to assign a landmark type based on
the values of the three computed indicators. Note that extraction of line landmarks is explained in the next section.
As for the places which have been found only by 3DCG
methods, 0 is assigned as the values of their visit popularity
and indirect visibility.
We determine “Area landmark” if the values of either indirect visibility or direct visibility of a place are high. Theplaces characterized only by high visit popularity are regarded as point landmarks.
2.5 Extracting Line Landmarks
We detect crowded streets and consider them as line landmarks by measuring visit popularity of streets using the analyzed tweets. We first extract the set of crowded intersections which are determined based on the number of tweets
assigned to these intersections. Next, we search for the set of684

情報処理学会 インタラクション 2016
IPSJ Interaction 2016

sequential crowded intersections corresponding to segmentsof the same street. Each street is weighted by the total number of tweets sent from its respective crowded intersections.
The value of weight of each street is then considered as visit
popularity of the street.

3.

Experiments

We developed an online prototype system [3] forlandmark-based route recommendation for San Francisco,
Kagoshima and Kyoto cities (Fig. 2). The system is evaluated in a virtual space by simulating the real world using
Google Street View (SV) whose validity is also tested.
3.1 Datasets
We introduce datasets of SF city. 0.6M (millions) tweets
are extracted. Then, the prototype system filters out tweetsof users who had emitted 5, 000 and more tweets during
the periods. Consequently, 0.57M tweets are utilized as
the tweets dataset. We have constructed a database ofplaces in SF city by gathering 25K places’ basic attributes
and crowd-sourced statistics from Foursquare which are asnapshot data. In terms of geographic information, fortunately, various datasets concerning SF city are provided inSF OpenData.
3.2

Extracted Landmarks and Recommended
Routes2, 604 popular places were detected and 15 places withhigh indirect visibility were extracted. Based on this, 10places were classified as area landmarks. Furthermore, inorder to detect area landmarks by 3DCG based method, weselected the top 10 tallest buildings in each block. In total,
549 area landmarks were extracted based on their visibility
from each intersection. Then the system detected 45 streets.
By using these landmarks the system constructed a routegraph and searched for a shorter route consisting of fewer
landmarks. More details of the route graph construction
and route search processes are provided in [6].
3.3 Evaluation
3.3.1 Settings
In order to evaluate routes we compare our proposed system with an existing route search system: Google Directions(GR). Furthermore, in order to confirm the usefulness of using crowd footprint data, we search for two types of routes by
the proposed system. One (LR) uses landmarks extracted
by considering both indirect visibility and direct visibility
measured using both tweets and geographic data, and theother (V R) uses landmarks extracted by considering direct
visibility measured using geographic data only.
In this study, 36 participants (28 males and 8 females) who
have never been to San Francisco participated. They firstreceived a route recommendation from a starting point toa destination and tried to remember it within 2 min. Then
relying on their memory, they attempted to reach the des-162C50
2016/3/3

tination in a simulated real space by operating SV*1 . The
materials about the recommended routes which were shown
to the users included textual route directions from a starting
point to a destination and a route path displayed on a map
as well as images of landmarks, if any were included in theroutes (see Fig. 3). During the experiments, these materials
and a small screen enabling a participant to check his/hercurrent location on a map (which is typically shown in thecorner of the SV interface) were hidden from users unlessthe subjects asked to see them.
In order to evaluate recommended routes, we set threeevaluation items as follows:i) time (min.): How long did it take to reach a destination from a starting point?
ii) route ref.: How many times did you check route directions on a printed material about the route?
iii) self-position ref.: How many times did you checkyour self-position with Google Maps?
We recorded i) the time spent from a starting point to adestination, ii) a route directions’ reference count, and iii)
a self-position’s reference count during each participant’s
trial. Users were asked not to check the route directions andtheir own locations as much as possible until they got lost.
Note that the route directions with useful landmarks can
include virtual paths indicating corresponding area landmarks. Therefore, they freely moved toward next landmarks
from point/line landmarks connecting virtual paths. Whencalculating the distance of a virtual path, we used the distance of shortest routes between two points of the path.
We prepared three pairs of a starting point and a destination. Note that the pairs were randomly selected not
to be the same routes by our method as those by GoogleDirections. Then we search for routes by the three methods per pair of a starting point and a destination. As aresult, we got 9 routes: 3 routes using landmarks extracted
based on both indirect visibility and direct visibility (LR1to LR3 ), 3 routes using landmarks extracted based on direct visibility for only tall buildings by 3DCG-based method(V R1 to V R3 ), and 3 routes by Google Directions (GR1 toGR3 ). Finally, we evaluated 8 unique routes because LR3and V R3 were the same. We conducted this study by dividing participants into groups such that each group always
tested routes with diﬀerent origin and destination.
3.3.2 Results
We present routes by the three methods in Figs. 3. Fig. 3
shows three routes between start2 and goal2 : (a) LR2 isa route with landmarks extracted by considering the threeindicators of landmark’s utility, V R2 is a route with landmarks extracted by 3DCG-based method which determine
direct visibility for only tall buildings, and GR2 is a route
searched by Google Directions walking mode (GR2 ). On average, the landmark-based routes were simpler than routes
by Google Directions on the actual road network.
In order to compare the three methods: LR, VR, andGR, we show results of the three evaluation items for routes*1© 2016 Information Processing Society of Japan

We asked that participants should use a cross key.

685

情報処理学会 インタラクション 2016
IPSJ Interaction 2016

162C502016/3/3(a) Route search by LR(b) Route search by V R

Fig. 2: Images of the prototype system [3].

Fig. 3: Examples of routes between start2 and goal2 by thethree methods (LR, VR, and GR). Note that a stadium is
not tall, and thus, only visible from nearby, whereas there
are many cues wide spread such as flags indicated in (a).

Fig. 4: Boxplots of the evaluation items for routes in SF.
as shown in Fig. 4. As a result, we found that the average time of LR was shorter than the other two methods.
Furthermore, the deviation of route and self-position’s reference count were smaller than others. This means that it
is free from influence of a potential error due to diﬀerent
user’s skills. In addition, the frequency of checking the selfposition and route directions were decreased compared withGR. Then, significant diﬀerences (<0.05) in route directions’reference count and self-position’s reference count were also
observed by comparing LR to GR.

4.

Conclusions

In this paper, we proposed a method to detect useful© 2016 Information Processing Society of Japan

landmarks by measuring visit popularity, indirect visibility, and direct visibility by exploiting geo-tagged tweets
data collected from Twitter, places and check-ins data from
Foursquare, and geographical data obtained from digital
maps. Having detected landmarks, we construct a routegraph, which can eﬃciently find optimal paths in terms ofthe number of landmarks as well as path lengths. In theexperiments, we confirm that routes with landmarks whichwere extracted by considering both indirect visibility and direct visibility were easier to remember and follow than theroutes with landmarks which were extracted by considering
direct visibility only and the routes by Google Directions,in terms of taking time from a starting point to destination,
self-position’s reference count, and route directions’ reference count.
In the future work, we plan to test with other cities forvalidating the proposed approach. In addition, we will analyze tweet content in detail for extracting more semantic features of landmarks. Psychological and social analysis might
be another interesting research topic.
Acknowledgments This research was supported inpart by Strategic Information and Communications R&D
Promotion Programme (SCOPE), the Ministry of Internal
Aﬀairs and Communications of Japan, and JSPS KAKENHI
Grant Numbers 26280042 and 15K00162.
References
[1]
[2]
[3]
[4]
[5]
[6]

P.-E. Michon and M. Denis. When and why are visual landmarks used in giving directions? In Spatial Information Theory, vol. 2205, pp. 292-305. 2001.
K. Lynch. The Image of the City. MIT Press, 1960.
Landmark Navi Beta (Online demo) http://www.ibe.
kagoshima-u.ac.jp/~lmnavi/index_jp.html.
R. Yonekura, Y. Akagi, S. Ono, Y. Kawai, and H. Kawasaki.
Navigation system which uses visibility map of landmarks toreduce reference count of the map. In IEVC ’14, 2014.
E. Antoine, A. Jatowt, S. Wakamiya, Y. Kawai, and T.
Akiyama. Portraying collective spatial attention in twitter.
In KDD ’15, pp. 39-48, 2015.
R. Yonekura, H. Morinaga, S. Wakamiya, Y. Akagi, S. Ono,
Y. Kawai, H. Kawasaki. Navigation System without Explicit
Route Presentation using Point, Line and Area based Landmarks. In Interaction2015, 2015.

686